A general theorem in spectral extremal graph theory
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866918224908517376 |
|---|---|
| author | Byrne, John Desai, Dheer Noal Tait, Michael |
| author_facet | Byrne, John Desai, Dheer Noal Tait, Michael |
| contents | The extremal graphs $\mathrm{EX}(n,\mathcal F)$ and spectral extremal graphs $\mathrm{SPEX}(n,\mathcal F)$ are the sets of graphs on $n$ vertices with maximum number of edges and maximum spectral radius, respectively, with no subgraph in $\mathcal F$. We prove a general theorem which allows us to characterize the spectral extremal graphs for a wide range of forbidden families $\mathcal F$ and implies several new and existing results. In particular, whenever $\mathrm{EX}(n,\mathcal F)$ contains the complete bipartite graph $K_{k,n-k}$ (or certain similar graphs) then $\mathrm{SPEX}(n,\mathcal F)$ contains the same graph when $n$ is sufficiently large. We prove a similar theorem which relates $\mathrm{SPEX}(n,\mathcal F)$ and $\mathrm{SPEX}_α(n,\mathcal F)$, the set of $\mathcal F$-free graphs which maximize the spectral radius of the matrix $A_α=αD+(1-α)A$, where $A$ is the adjacency matrix and $D$ is the diagonal degree matrix. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2401_07266 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A general theorem in spectral extremal graph theory Byrne, John Desai, Dheer Noal Tait, Michael Combinatorics 05C35, 05C50 The extremal graphs $\mathrm{EX}(n,\mathcal F)$ and spectral extremal graphs $\mathrm{SPEX}(n,\mathcal F)$ are the sets of graphs on $n$ vertices with maximum number of edges and maximum spectral radius, respectively, with no subgraph in $\mathcal F$. We prove a general theorem which allows us to characterize the spectral extremal graphs for a wide range of forbidden families $\mathcal F$ and implies several new and existing results. In particular, whenever $\mathrm{EX}(n,\mathcal F)$ contains the complete bipartite graph $K_{k,n-k}$ (or certain similar graphs) then $\mathrm{SPEX}(n,\mathcal F)$ contains the same graph when $n$ is sufficiently large. We prove a similar theorem which relates $\mathrm{SPEX}(n,\mathcal F)$ and $\mathrm{SPEX}_α(n,\mathcal F)$, the set of $\mathcal F$-free graphs which maximize the spectral radius of the matrix $A_α=αD+(1-α)A$, where $A$ is the adjacency matrix and $D$ is the diagonal degree matrix. |
| title | A general theorem in spectral extremal graph theory |
| topic | Combinatorics 05C35, 05C50 |
| url | https://arxiv.org/abs/2401.07266 |