On the first two eigenvalues of regular graphs
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914627795812352 |
|---|---|
| author | Zhang, Shengtong |
| author_facet | Zhang, Shengtong |
| contents | Let $G$ be a regular graph with $m$ edges, and let $μ_1, μ_2$ denote the two largest eigenvalues of $A_G$, the adjacency matrix of $G$. We show that, if $G$ is not complete, then
$$μ_1^2 + μ_2^2 \leq \frac{2(ω- 1)}ω m$$
where $ω$ is the clique number of $G$. This confirms a conjecture of Bollobás and Nikiforov for regular graphs. We also show that equality holds if and only if $G$ is either a balanced Turán graph or the disjoint union of two balanced Turán graphs of the same size. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2309_08184 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | On the first two eigenvalues of regular graphs Zhang, Shengtong Combinatorics Spectral Theory Let $G$ be a regular graph with $m$ edges, and let $μ_1, μ_2$ denote the two largest eigenvalues of $A_G$, the adjacency matrix of $G$. We show that, if $G$ is not complete, then $$μ_1^2 + μ_2^2 \leq \frac{2(ω- 1)}ω m$$ where $ω$ is the clique number of $G$. This confirms a conjecture of Bollobás and Nikiforov for regular graphs. We also show that equality holds if and only if $G$ is either a balanced Turán graph or the disjoint union of two balanced Turán graphs of the same size. |
| title | On the first two eigenvalues of regular graphs |
| topic | Combinatorics Spectral Theory |
| url | https://arxiv.org/abs/2309.08184 |