학술

The Bollob\'as--Nikiforov inequality for complete multipartite graphs, with remarks on the $K_4$-free case

arXiv Math
CC BY
이 매체는 공공·자유 라이선스로 본문을 직접 표시합니다.

Abstract

Bollobás and Nikiforov conjectured that every graph $G \neq K_n$ with $m$ edges and clique number $\omega$ satisfies $\lambda_1^2(G) + \lambda_2^2(G) \leq 2(1 - 1/\omega)m$, where $\lambda_1(G) \geq \lambda_2(G)$ are the two largest adjacency eigenvalues.

We give a short self-contained proof of the inequality for complete multipartite graphs, based on a quadratic-form identity which shows that $\lambda_2 \leq 0$, and we determine the equality cases in this class.

We show that equality in the conjecture is attained by a wider family than the Turán graphs, namely by disjoint unions of two complete bipartite graphs, or of two balanced complete $r$-partite graphs of possibly different orders.

For $K_4$-free graphs we record the cases that follow from known results, with corrected attributions, and we give examples showing that three natural lines of attack fail: a Hoffman-type eigenvalue bound for graphs with large independence number, a spectral stability statement for connected graphs, and Zykov symmetrization in an arbitrary direction.

관련 뉴스