The Bollobás--Nikiforov Conjecture for Complete Multipartite Graphs and Dense $K_4$-Free Graphs
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915929213894656 |
|---|---|
| author | Giacomelli, Piero |
| author_facet | Giacomelli, Piero |
| contents | The Bollobás--Nikiforov conjecture asserts that for any graph $G \neq K_n$ with $m$ edges and clique number $ω(G)$, \[
λ_1^2(G) + λ_2^2(G)
\;\leq\;
2\!\left(1 - \frac{1}{ω(G)}\right)m, \] where $λ_1(G) \geq λ_2(G) \geq \cdots \geq λ_n(G)$ are the adjacency eigenvalues of $G$. We prove the conjecture for all complete multipartite graphs $K_{n_1,\ldots,n_r}$ with $n_1 + \cdots + n_r > r$. The proof computes the full spectrum via a secular equation, establishes that $λ_2 = 0$ whenever the graph has more vertices than parts, and then applies Nikiforov's spectral Turán theorem; equality holds if and only if all parts have equal size. We also prove a stability result for $K_4$-free graphs whose spectral radius is near the Turán maximum: such graphs are structurally close to the balanced complete tripartite graph, and as a consequence the conjecture holds for all $K_4$-free graphs with $m = Ω(n^2)$ when $n$ is sufficiently large. Finally, we identify the precise obstruction preventing a Hoffman-bound approach from settling the conjecture for $K_4$-free graphs with independence number $α(G) \geq n/3$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_26379 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | The Bollobás--Nikiforov Conjecture for Complete Multipartite Graphs and Dense $K_4$-Free Graphs Giacomelli, Piero Combinatorics 05C50 05C35 The Bollobás--Nikiforov conjecture asserts that for any graph $G \neq K_n$ with $m$ edges and clique number $ω(G)$, \[ λ_1^2(G) + λ_2^2(G) \;\leq\; 2\!\left(1 - \frac{1}{ω(G)}\right)m, \] where $λ_1(G) \geq λ_2(G) \geq \cdots \geq λ_n(G)$ are the adjacency eigenvalues of $G$. We prove the conjecture for all complete multipartite graphs $K_{n_1,\ldots,n_r}$ with $n_1 + \cdots + n_r > r$. The proof computes the full spectrum via a secular equation, establishes that $λ_2 = 0$ whenever the graph has more vertices than parts, and then applies Nikiforov's spectral Turán theorem; equality holds if and only if all parts have equal size. We also prove a stability result for $K_4$-free graphs whose spectral radius is near the Turán maximum: such graphs are structurally close to the balanced complete tripartite graph, and as a consequence the conjecture holds for all $K_4$-free graphs with $m = Ω(n^2)$ when $n$ is sufficiently large. Finally, we identify the precise obstruction preventing a Hoffman-bound approach from settling the conjecture for $K_4$-free graphs with independence number $α(G) \geq n/3$. |
| title | The Bollobás--Nikiforov Conjecture for Complete Multipartite Graphs and Dense $K_4$-Free Graphs |
| topic | Combinatorics 05C50 05C35 |
| url | https://arxiv.org/abs/2603.26379 |