Two conjectured strengthenings of Turán's theorem

DOI10.1016/J.LAA.2023.12.010arXiv2101.05229OpenAlexW4389720797MaRDI QIDQ6141065FDOQ6141065

Authors: Clive Elphick, William Linz, Pawel Wocjan 

Publication date: 22 January 2024

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

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.

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

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

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)

Cites Work

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

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)