Samenvatting
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.
| Originele taal-2 | Engels |
|---|---|
| Pagina's (van-tot) | 19-45 |
| Aantal pagina's | 27 |
| Tijdschrift | Linear Algebra and Its Applications |
| Volume | 702 |
| DOI's | |
| Status | Gepubliceerd - 1 dec. 2024 |
Financiering
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.
| Financiers | Financiernummer |
|---|---|
| Nederlandse Organisatie voor Wetenschappelijk Onderzoek | VI.Vidi.213.085 |