Two conjectured strengthenings of Turán's theorem

DOI10.1016/J.LAA.2023.12.010MaRDI QIDQ6141065zbMATH OpenOpenAlexFDO

Authors Clive Elphick, William Linz, Pawel Wocjan

Publication date 22 January 2024

Published in Linear Algebra and its Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2101.05229

zbMATH Keywords

clique numberpositive eigenvaluesspectral Turán theorem

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Eigenvalues, singular values, and eigenvectors (15A18)

Abstract: Let $m{u}_{1}geldotsgem{u}_n$ denote the eigenvalues of a graph $G$ with $m$ edges and clique number $omega(G)$. Nikiforov proved a spectral version of Tur'an's theorem that [ mu_1^2 le frac{2m(omega - 1)}{omega}, ] and Bollob'as and Nikiforov conjectured that for $Got=K_n$ [ mu_1^2 + mu_2^2 le frac{2m(omega - 1)}{omega}. ] This paper proposes the conjecture that for all graphs $(m{u}_1^2+m{u}_2^2)$ in this inequality can be replaced by the sum of the squares of the $omega$ largest eigenvalues, provided they are positive. We prove the conjecture for weakly perfect, Kneser, Johnson and classes of strongly regular graphs. We also provide experimental evidence and describe how the bound can be applied.

Recommendations

• On the first two eigenvalues of regular graphs
• Signed spectral Turań-type theorems
• Eigenvalues and triangles in graphs
• On a conjecture of spectral extremal problems
• A Brualdi-Hoffman-Turán problem on cycles

Cites work

• scientific article; zbMATH DE number 1600999 (Why is no real title available?)
• scientific article; zbMATH DE number 3668627 (Why is no real title available?)
• A bound on the spectral radius of graphs with \(e\) edges
• An inertial lower bound for the chromatic number of a graph
• Bounds of eigenvalues of graphs
• Cliques and the spectral radius
• Cliques in random graphs
• Conjectured bounds for the sum of squares of positive eigenvalues of a graph
• Eigenvalues and triangles in graphs
• Erdős-Ko-Rado theorems. Algebraic approaches
• Lower bounds for the clique and the chromatic numbers of a graph
• New spectral bounds on the chromatic number encompassing all eigenvalues of the adjacency matrix
• On the clique number of integral circulant graphs
• Proof of a conjectured lower bound on the chromatic number of a graph
• Some Inequalities for the Largest Eigenvalue of a Graph
• Some eigenvalue properties in graphs (conjectures of Graffiti -- II)
• Spectral bounds for the clique and independence numbers of graphs
• Upper bounds for the achromatic and coloring numbers of a graph

Cited in

(2)

• A Brualdi-Hoffman-Turán problem on cycles
• On the first two eigenvalues of regular graphs

This page was built for publication: Two conjectured strengthenings of Turán's theorem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6141065)