Eigenvalues of K1,k-Free Graphs and the Connectivity of Their Independence Complexes

Ron Aharoni, Noga Alon, Eli Berger

Research output: Contribution to journalArticle

3 Scopus citations

Abstract

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

Original languageEnglish (US)
Pages (from-to)384-391
Number of pages8
JournalJournal of Graph Theory
Volume83
Issue number4
DOIs
StatePublished - Dec 1 2016
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Geometry and Topology

Keywords

  • Eigenvalues
  • homological connectivity
  • independent transversals

Fingerprint Dive into the research topics of 'Eigenvalues of <sub>K1,k</sub>-Free Graphs and the Connectivity of Their Independence Complexes'. Together they form a unique fingerprint.

  • Cite this