Spectral saturation: inverting the spectral Turán theorem

MaRDI QIDQ1010943zbMATH OpenFDO

Authors Vladimir Nikiforov

Publication date 7 April 2009

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0711.3488, https://eudml.org/doc/129765, http://www.emis.de/journals/EJC/Volume_16/Abstracts/v16i1r33.html

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

stability resultscomplete r-partite graphr-partite Turan graph

Mathematics Subject Classification ID

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

Abstract: We prove that if the spectral radius of a graph G of order n is larger than the spectral radius of the r-partite Turan graph of the same order, then G contains various supergraphs of the complete graph of order r+1. In particular G contains a complete r-partite graph of size log n with one edge added to the first part. These results complete a project of Erdos from 1963. We also give corresponding stability results.

Recommendations

• Turán's theorem inverted
• Stability for large forbidden subgraphs
• A spectral Erdős-Stone-Bollobás theorem
• Large joints in graphs
• Strong Turán stability

Cited in

(14)

• The spectral radius of graphs with no odd wheels
• Extremal problems for the p-spectral radius of graphs
• A spectral Erdős-Rademacher theorem
• Spectral extremal graphs for intersecting cliques
• Turán's theorem inverted
• Stability for large forbidden subgraphs
• On the eccentric distance sum of graphs
• A strengthening of the spectral chromatic critical edge theorem: Books and theta graphs
• On a conjecture of spectral extremal problems
• Spectral extremal problem on disjoint color-critical graphs
• A spectral Erdős-Stone-Bollobás theorem
• Spectral extremal graphs for the bowtie
• A unique characterization of spectral extrema for friendship graphs
• Counting substructures and eigenvalues. I: Triangles

This page was built for publication: Spectral saturation: inverting the spectral Turán theorem

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