Eigenvalues of    K   1  ,  k    ‐Free Graphs and the Connectivity of Their Independence Complexes | Zendy

Aharoni Ron | Zendy; Alon Noga | Zendy; Berger Eli | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

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.

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here

Accelerating Research