Eigenvalues of K1, k‐Free Graphs and the Connectivity of Their Independence Complexes. Issue 4 (20th November 2015)

• Record Type: Journal Article
• Authors: Aharoni, Ron; Alon, Noga; Berger, Eli
• Is Part Of: Journal of graph theory. Volume 83:Issue 4(2016)
• Page Start: 384
• Page End: 391
• Publication Date: 2015-11-20
• Subjects: Eigenvalues -- homological connectivity -- independent transversals; Graph theory -- Periodicals; 511
• DOI: 10.1002/jgt.22004
• Languages: English
• ISSNs: 0364-9024

Abstract

Abstract: Let G be a graph on n vertices, with maximal degree d, and not containing K 1, k as an induced subgraph. We prove: 1. λ ( G ) ≤ ( 2 − 1 2 k − 2 + o ( 1 ) ) d 2. η ( 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.