### 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 | |

State | Published - Dec 1 2016 |

Externally published | Yes |

### 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

Aharoni, R., Alon, N., & Berger, E. (2016). Eigenvalues of

_{K1,k}-Free Graphs and the Connectivity of Their Independence Complexes.*Journal of Graph Theory*,*83*(4), 384-391. https://doi.org/10.1002/jgt.22004