A unified framework for the Expander Mixing Lemma for irregular graphs and its applications
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866929421615628288 |
|---|---|
| author | Abiad, Aida Zeijlemaker, Sjanne |
| author_facet | Abiad, Aida Zeijlemaker, Sjanne |
| contents | 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 regularise 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2401_07125 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A unified framework for the Expander Mixing Lemma for irregular graphs and its applications Abiad, Aida Zeijlemaker, Sjanne Combinatorics 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 regularise 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. |
| title | A unified framework for the Expander Mixing Lemma for irregular graphs and its applications |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2401.07125 |