EUVIMEDEUVIMED entdecken
Crossref

A Robust Bollobás-Nikiforov Bound for Graphs Close to Triangle-Free Graphs

Yong Lu

The Electronic Journal of Combinatorics · 06.11.2026 · 33 (4)

DOI: 10.37236/15969 ↗

Kurz gefasst

Fachartikel in der Zeitschrift The Electronic Journal of Combinatorics, online erschienen am 06.11.2026. Verfasst von Yong Lu.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

The Bollobás-Nikiforov (BN) conjecture, in its clique-number form, asserts that every non-complete graph $G$ of order $n$ with $m$ edges and clique number $\omega(G)$ satisfies\[\lambda_1(G)^2+\lambda_2(G)^2\le 2\left(1-\frac1{\omega(G)}\right)m,\]where $\lambda_1(G)\ge \lambda_2(G)\ge\cdots\ge\lambda_n(G)$ are the adjacency eigenvalues of $G$.We prove an unconditional perturbative form for graphs that can be made triangle-free by deleting few edges. Let $\eta_{\triangle}(G)$ be the minimum number of edges whose deletion destroys all triangles of $G$. Every non-complete graph $G$ on at least two vertices satisfies\[\lambda_1(G)^2+\lambda_2(G)^2\le 2\left(1-\frac1\omega\right)m+C_\omega \eta_{\triangle}(G),\]where $\omega=\omega(G)$ and\[C_\omega=2+\frac2\omega+\frac{4\omega}{\omega-2}\qquad (\omega\ge3).\]For $\omega=1,2$, no additive error is needed. Since $C_\omega\le 44/3$, a uniform error term $(44/3) \eta_{\triangle}(G)$ is valid. The emphasis of the result is the explicit finite error that is linear in the edge-deletion distance from the triangle-free class. We also show that the vertex-disjoint triangle packing number cannot replace $\eta_{\triangle}(G)$ in this perturbative framework, and we clarify the relation with bounds expressed in terms of the total number of triangles.

Zitieren

APA

Lu, Y. (2026). A Robust Bollobás-Nikiforov Bound for Graphs Close to Triangle-Free Graphs. The Electronic Journal of Combinatorics, 33(4). https://doi.org/10.37236/15969

Vancouver

Lu Y. A Robust Bollobás-Nikiforov Bound for Graphs Close to Triangle-Free Graphs. The Electronic Journal of Combinatorics. 2026;33(4). doi:10.37236/15969

BibTeX
@article{Lu2026,
  author = {Lu, Yong},
  title = {A Robust Bollobás-Nikiforov Bound for Graphs Close to Triangle-Free Graphs},
  journal = {The Electronic Journal of Combinatorics},
  year = {2026},
  volume = {33},
  number = {4},
  doi = {10.37236/15969}
}
Kostenlos starten →