Refinement on Spectral Turán’s Theorem

DOI10.1137/22M1507814zbMATH Open1525.05115arXiv2204.09194OpenAlexW4387779699MaRDI QIDQ6081801

Yue Jian Peng, Yongtao Li

Publication date: 26 October 2023

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Abstract: A well-known result in extremal spectral graph theory, known as Nosal's theorem, states that if $G$ is a triangle-free graph on $n$ vertices, then $lambda(G)lelambda(K_{lfloorfracn2floor,lceilfracn2ceil})$, equality holds if and only if $G=K_{lfloorfracn2floor,lceilfracn2ceil}$. Nikiforov [Linear Algebra Appl. 427 (2007)] extended Nosal's theorem to $K_{r+1}$-free graphs for every integer $rge2$. This is known as the spectral Tur'{a}n theorem. Recently, Lin, Ning and Wu [Combin. Probab. Comput. 30 (2021)] proved a refinement on Nosal's theorem for non-bipartite triangle-free graphs. In this paper, we provide alternative proofs for the result of Nikiforov and the result of Lin, Ning and Wu. Our proof can allow us to extend the later result to non-$r$-partite $K_{r+1}$-free graphs. Our result refines the theorem of Nikiforov and it also can be viewed as a spectral version of a theorem of Brouwer.

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

zbMATH Keywords

spectral radiusTurán theoremZykov symmetrization

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Enumeration in graph theory (05C30) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Sharp bounds for the signless Laplacian spectral radius in terms of clique number
• Extremal problems for the \(p\)-spectral radius of graphs
• Eigenvalues of complete multipartite graphs
• A proof of the stability of extremal graphs, Simonovits' stability from Szemerédi's regularity
• Signless Laplacian spectral radii of graphs with given chromatic number
• The typical structure of graphs with no large cliques
• Spectral radii of graphs with given chromatic number
• More spectral bounds on the clique and independence numbers
• Spectral bounds for the clique and independence numbers of graphs
• Large dense neighbourhoods and Turán's theorem
• Dense neighbourhoods and Turan's theorem
• A relation between the signless Laplacian spectral radius of complete multipartite graphs and majorization
• On the spectrum of an equitable quotient matrix and its application
• Spectral extrema of graphs with fixed size: cycles and complete bipartite graphs
• A spectral condition for the existence of a pentagon in non-bipartite graphs
• The maximum spectral radius of non-bipartite graphs forbidding short odd cycles
• Spectral extremal graphs for intersecting cliques
• The spectral radius of graphs with no intersecting odd cycles
• The maximum spectral radius of graphs without friendship subgraphs
• A spectral version of Mantel's theorem
• Adjacency eigenvalues of graphs without short odd cycles
• The spectral radius of graphs with no odd wheels
• A spectral condition for odd cycles in non-bipartite graphs
• Analytic methods for uniform hypergraphs
• The \(p\)-spectral radius of \(k\)-partite and \(k\)-chromatic uniform hypergraphs
• Spectral extrema for graphs: the Zarankiewicz problem
• Three conjectures in extremal spectral graph theory
• Bounds on graph eigenvalues. II
• Maximum \(K_{r+1}\)-free graphs which are not \(r\)-partite.
• Cliques and the spectral radius
• On a conjecture of spectral extremal problems
• A spectral condition for the existence of cycles with consecutive odd lengths in non-bipartite graphs
• On the non-(p-1)-partite K_{p}-free graphs
• Some new results in extremal graph theory
• Some Inequalities for the Largest Eigenvalue of a Graph
• Eigenvalues and triangles in graphs
• Spectral Extremal Problems for Hypergraphs
• Maxima for Graphs and a New Proof of a Theorem of Turán
• The Minimum Number of Triangular Edges and a Symmetrization Method for Multiple Graphs
• The History of Degenerate (Bipartite) Extremal Graph Problems
• Strong Turán stability
• Proofs from THE BOOK
• Ramsey-Turán theory
• A complete solution to the Cvetković–Rowlinson conjecture
• Maxima of the \(Q\)-index of non-bipartite \(C_3\)-free graphs

Related Items (6)

Spectral extremal graphs for the bowtie ⋮ A spectral extremal problem on non-bipartite triangle-free graphs ⋮ Spectral radius of graphs with given size and odd girth ⋮ Spectral extremal graphs without intersecting triangles as a minor ⋮ A spectral Erdős-Rademacher theorem ⋮ Note on Mantel theorem and Turán theorem

This page was built for publication: Refinement on Spectral Turán’s Theorem