On graphs with large third eigenvalue
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866915782232899584 |
|---|---|
| author | Leonida, Giacomo Li, Sida |
| author_facet | Leonida, Giacomo Li, Sida |
| contents | Given a graph $G$, let $λ_3$ denote the third largest eigenvalue of its adjacency matrix. In this paper, we prove various results towards the conjecture that $λ_3(G) \le \frac{|V(G)|}{3}$, motivated by a question of Nikiforov. We generalise the known constructions that yield $λ_3(G) = \frac{|V(G)|}{3} - 1$ and prove the inequality holds for $G$ strongly regular, a regular line graph or a Cayley graph on an abelian group. We also consider the extended problem of minimising $λ_{n-1}$ on weighted graphs and reduce the existence of a minimiser with simple final eigenvalue to a vertex multiplication of a graph on 11 vertices. We prove that the minimal $λ_{n-1}$ over weighted graphs is at most $O(\sqrt{n})$ from the minimal $λ_{n-1}$ over unweighted graphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_02563 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On graphs with large third eigenvalue Leonida, Giacomo Li, Sida Combinatorics 15A42, 05C50 Given a graph $G$, let $λ_3$ denote the third largest eigenvalue of its adjacency matrix. In this paper, we prove various results towards the conjecture that $λ_3(G) \le \frac{|V(G)|}{3}$, motivated by a question of Nikiforov. We generalise the known constructions that yield $λ_3(G) = \frac{|V(G)|}{3} - 1$ and prove the inequality holds for $G$ strongly regular, a regular line graph or a Cayley graph on an abelian group. We also consider the extended problem of minimising $λ_{n-1}$ on weighted graphs and reduce the existence of a minimiser with simple final eigenvalue to a vertex multiplication of a graph on 11 vertices. We prove that the minimal $λ_{n-1}$ over weighted graphs is at most $O(\sqrt{n})$ from the minimal $λ_{n-1}$ over unweighted graphs. |
| title | On graphs with large third eigenvalue |
| topic | Combinatorics 15A42, 05C50 |
| url | https://arxiv.org/abs/2501.02563 |