Abstract
A unified framework for the Expander Mixing Lemma for irregular graphs using adjacency eigenvalues is presented, as well as two new versions of it. While the existing Expander Mixing Lemmas for irregular graphs make use of the notion of volume (the sum of degrees within a vertex set), we instead propose to use the Perron eigenvector entries as vertex weights, which is a way to regularize the graph. This provides a new application of weight partitions of graphs. The new Expander Mixing Lemma versions are then applied to obtain several eigenvalue bounds for NP-hard parameters such as the zero forcing number, the vertex integrity and the routing number of a graph.
| Original language | English |
|---|---|
| Pages (from-to) | 19-45 |
| Number of pages | 27 |
| Journal | Linear Algebra and Its Applications |
| Volume | 702 |
| DOIs | |
| Publication status | Published - 1 Dec 2024 |
Funding
Aida Abiad is supported by the Dutch Research Council through the grant VI.Vidi.213.085. The authors thank the referee for the many detailed comments. The authors would also like to thank Sam Adriaensen and Mike T8 for inspiring discussions.
| Funders | Funder number |
|---|---|
| Nederlandse Organisatie voor Wetenschappelijk Onderzoek | VI.Vidi.213.085 |
Keywords
- Adjacency eigenvalues
- Expander Mixing Lemma
- Irregular graphs