Refinement on Spectral Turán’s Theorem

DOI10.1137/22M1507814MaRDI QIDQ6081801zbMATH OpenOpenAlexFDO

Authors Yongtao Li, Yuejian Peng

Publication date 26 October 2023

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

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

zbMATH Keywords

spectral radiusTurán theoremZykov symmetrization

Mathematics Subject Classification ID

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

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.

Recommendations

• A spectral extremal problem on non-bipartite triangle-free graphs
• The maximum spectral radius of non-bipartite graphs forbidding short odd cycles
• Generalizing theorems of Nosal and Nikiforov: triangles and quadrilaterals
• On some papers of Nikiforov.

Cites work

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

Cited in

(24)

• On a generalization of the spectral Mantel's theorem
• 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
• A spectral Erdős-Rademacher theorem
• Spectral extremal graphs without intersecting triangles as a minor
• Note on Mantel theorem and Turán theorem
• Non-r-partite graphs without complete split subgraphs
• A spectral generalized Alon-Frankl theorem
• A spectral version of the theorem of Zykov and Erdős
• A spectral Erdős-Faudree-Rousseau theorem
• On the spectral extremal problem of planar graphs
• A spectral generalized Erdős-Gallai theorem
• Spectral extremal problems for non-bipartite graphs without odd cycles
• Spectral supersaturation: triangles and bowties
• Decomposition family and spectral extremal problems on non-bipartite graphs
• More results on the spectral radius of graphs with no odd wheels
• A refinement on spectral Mantel's theorem
• Spectral Turán problem of non-bipartite graphs: forbidden books
• Spectral extremal graphs for fan graphs
• Spectral skeletons and applications
• Non-bipartite graphs without theta subgraphs
• Turán number of books in non-bipartite graphs
• Stable structure and extremal eigenvalues of degenerate Turán problems

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

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