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

complete r-partite graphr-partite Turan graphstability results

Mathematics Subject Classification ID

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

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.

Review text

Summary: Let \(\mu(G)\) be the \(r\)-partite Turán graph of order \(n\). We prove that if \(G\) is a graph of order \(n\) with \(\mu(G) >\mu (T_{r}(n))\), then \(G\) contains various large supergraphs of the complete graph of order \(r+1,\) e.g., the complete \(r\)-partite graph with all parts of size \(\log n\) with an edge added to the first part. 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

(34)

• Turán's theorem inverted
• Spectral extremal graphs for intersecting cliques
• A unique characterization of spectral extrema for friendship graphs
• The spectral radius of graphs with no odd wheels
• On a conjecture of spectral extremal problems
• Counting substructures and eigenvalues. I: Triangles
• A spectral Erdős-Stone-Bollobás theorem
• Stability for large forbidden subgraphs
• Extremal problems for the p-spectral radius of graphs
• On the eccentric distance sum of graphs
• A strengthening of the spectral chromatic critical edge theorem: Books and theta graphs
• Spectral extremal graphs for the bowtie
• Spectral extremal problem on disjoint color-critical graphs
• A spectral Erdős-Rademacher theorem
• Non-r-partite graphs without complete split subgraphs
• A spectral generalized Alon-Frankl theorem
• The signless Laplacian spectral Turán problems for color-critical graphs
• Spectral conditions for the maximum subgraph edge-connectivity of graphs
• Spectral extremal problem on the fish graph
• A spectral version of the theorem of Zykov and Erdős
• On the spectral extremal problem of planar graphs
• A spectral generalized Erdős-Gallai theorem
• An extension of spectral Mantel's theorem on wheels
• Decomposition family and spectral extremal problems on non-bipartite graphs
• More results on the spectral radius of graphs with no odd wheels
• A max-min problem on spectral radius and connectedness of graphs
• The signless Laplacian spectral radius of book-free graphs
• Spectral Turán problem of non-bipartite graphs: forbidden books
• More on Nosal's spectral theorem: books and 4-cycles
• Non-bipartite graphs without theta subgraphs
• Turán number of books in non-bipartite graphs
• Some Turán-type results for the signless Laplacian spectral radius
• The -spectral Turán type problems for graphs
• Maximal Q-index: graphs without long wheels

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)