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

Ron Aharoni; Noga Alon; Eli Berger

doi:10.1002/jgt.22004

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

Ron Aharoni, Noga Alon, Eli Berger

Research output: Contribution to journal › Article › peer-review

10 Scopus citations

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/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 K_1,k-free graphs.

Original language	English (US)
Pages (from-to)	384-391
Number of pages	8
Journal	Journal of Graph Theory
Volume	83
Issue number	4
DOIs	https://doi.org/10.1002/jgt.22004
State	Published - Dec 1 2016
Externally published	Yes

All Science Journal Classification (ASJC) codes

Geometry and Topology
Discrete Mathematics and Combinatorics

Keywords

Eigenvalues
homological connectivity
independent transversals

Access to Document

10.1002/jgt.22004

Cite this

@article{bc2d45f935624a09994dab602ae09a81,

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

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.",

keywords = "Eigenvalues, homological connectivity, independent transversals",

author = "Ron Aharoni and Noga Alon and Eli Berger",

note = "Publisher Copyright: {\textcopyright} 2015 Wiley Periodicals, Inc.",

year = "2016",

month = dec,

day = "1",

doi = "10.1002/jgt.22004",

language = "English (US)",

volume = "83",

pages = "384--391",

journal = "Journal of Graph Theory",

issn = "0364-9024",

publisher = "Wiley-Liss Inc.",

number = "4",

}

TY - JOUR

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

AU - Aharoni, Ron

AU - Alon, Noga

AU - Berger, Eli

PY - 2016/12/1

Y1 - 2016/12/1

N2 - 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.

AB - 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.

KW - Eigenvalues

KW - homological connectivity

KW - independent transversals

UR - http://www.scopus.com/inward/record.url?scp=84947794030&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84947794030&partnerID=8YFLogxK

U2 - 10.1002/jgt.22004

DO - 10.1002/jgt.22004

M3 - Article

AN - SCOPUS:84947794030

SN - 0364-9024

VL - 83

SP - 384

EP - 391

JO - Journal of Graph Theory

JF - Journal of Graph Theory

IS - 4

ER -