Premium
Eigenvalues of K 1 , k ‐Free Graphs and the Connectivity of Their Independence Complexes
Author(s) -
Aharoni Ron,
Alon Noga,
Berger Eli
Publication year - 2016
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.22004
Subject(s) - mathematics , combinatorics , independence number , eigenvalues and eigenvectors , induced subgraph , graph , degree (music) , laplace operator , independence (probability theory) , discrete mathematics , laplacian matrix , vertex (graph theory) , mathematical analysis , statistics , physics , quantum mechanics , acoustics
Let G be a graph on n vertices, with maximal degree d , and not containing K 1 , kas an induced subgraph. We prove: 1.λ ( G ) ≤ ( 2 − 1 2 k − 2 + o ( 1 ) ) d2.η ( I ( G ) ) ≥ n ( k − 1 ) d ( 2 k − 3 ) + k − 1 .Here λ ( G ) is the maximal eigenvalue of the Laplacian of G , I ( G ) is the independence complex of G , and η ( C ) denotes the topological connectivity of a complex C plus 2. These results provide improved bounds for the existence of independent transversals in K 1 , k ‐free graphs.