Some new results in extremal graph theory

zbMath1244.05125arXiv1107.1121MaRDI QIDQ3089369

Vladimir Nikiforov

Publication date: 24 August 2011

Abstract: In recent years several classical results in extremal graph theory have been improved in a uniform way and their proofs have been simplified and streamlined. These results include a new ErdH{o}s-Stone-Bollob'as theorem, several stability theorems, several saturation results and bounds for the number of graphs with large forbidden subgraphs. Another recent trend is the expansion of spectral extremal graph theory, in which extremal properties of graphs are studied by means of eigenvalues of various matrices. One particular achievement in this area is the casting of the central results above in spectral terms, often with additional enhancement. In addition, new, specific spectral results were found that have no conventional analogs. All of the above material is scattered throughout various journals, and since it may be of some interest, the purpose of this survey is to present the best of these results in a uniform, structured setting, together with some discussions of the underpinning ideas.

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

Mathematics Subject Classification ID

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

Related Items (84)

Merging the A-and Q-spectral theories ⋮ Making K_r+1-free graphs r-partite ⋮ Spectral extremal graphs for intersecting cliques ⋮ On the spectral moment of graphs with given clique number ⋮ Unnamed Item ⋮ Signless Laplacian spectral radius of graphs without short cycles or long cycles ⋮ Spectral radius, edge-disjoint cycles and cycles of the same length ⋮ The spectral radius of graphs with no intersecting odd cycles ⋮ Spectral Radius on Linear $r$-Graphs without Expanded $K_{r+1}$ ⋮ A spectral condition for the existence of the square of a path ⋮ Three conjectures in extremal spectral graph theory ⋮ Sharp upper bounds on the \(Q\)-index of (minimally) 2-connected graphs with given size ⋮ On the spectral radius, energy and Estrada index of the Sombor matrix of graphs ⋮ Ordering the maxima of \(L\)-index and \(Q\)-index: graphs with given size and diameter ⋮ On the spectral radius of graphs without a star forest ⋮ The maximum spectral radius of wheel-free graphs ⋮ A unique characterization of spectral extrema for friendship graphs ⋮ Spectral extrema of \(K_{s,t}\)-minor free graphs -- on a conjecture of M. Tait ⋮ The spectral Turán problem about graphs with no 6-cycle ⋮ The signless Laplacian spectral radius of graphs with forbidding linear forests ⋮ A note on extremal results on directed acyclic graphs ⋮ Maximum planar subgraphs in dense graphs ⋮ On the spectral radius of minimally 2-(edge)-connected graphs with given size ⋮ Spectral extrema of graphs with bounded clique number and matching number ⋮ A strengthening of the spectral chromatic critical edge theorem: Books and theta graphs ⋮ On the \(A_\alpha \)-spectral radius of graphs with given size ⋮ On a generalization of the spectral Mantel's theorem ⋮ Spectral extremal graphs for the bowtie ⋮ On the \(\alpha\)-index of minimally 2-connected graphs with given order or size ⋮ Maximizing the signless Laplacian spectral radius of minimally 3-connected graphs with given size ⋮ Some extremal problems for hereditary properties of graphs ⋮ Extremal problems for the \(p\)-spectral radius of graphs ⋮ Extensions on spectral extrema of \(C_5/C_6\)-free graphs with given size ⋮ Refinement on Spectral Turán’s Theorem ⋮ On a conjecture of spectral extremal problems ⋮ The maximum spectral radius of graphs without spanning linear forests ⋮ An \(A_\alpha\)-spectral Erdős-Pósa theorem ⋮ On \(A_{\alpha}\) spectral extrema of graphs forbidding even cycles ⋮ Spectral radius of graphs of given size with forbidden subgraphs ⋮ The index of signed graphs with forbidden subgraphs ⋮ The bipartite Turán number and spectral extremum for linear forests ⋮ Some extremal problems on \(A_\alpha \)-spectral radius of graphs with given size ⋮ Upper bounds of spectral radius of symmetric matrices and graphs ⋮ A spectral extremal problem on non-bipartite triangle-free graphs ⋮ Spectral radius of graphs with given size and odd girth ⋮ Spectral extremal problem on disjoint color-critical graphs ⋮ An \(A_{\alpha}\)-spectral Erdős-Sós theorem ⋮ The spectral radius of minor-free graphs ⋮ The maximum spectral radius of graphs of given size with forbidden subgraph ⋮ A spectral condition for the existence of cycles with consecutive odd lengths in non-bipartite graphs ⋮ Counting substructures and eigenvalues. I: Triangles ⋮ The maximum spectral radius of graphs without friendship subgraphs ⋮ Unnamed Item ⋮ The spectral radius of graphs without long cycles ⋮ The signless Laplacian spectral radius of graphs without intersecting odd cycles ⋮ Spectral analogues of Moon-Moser's theorem on Hamilton paths in bipartite graphs ⋮ Spectral extremal graphs without intersecting triangles as a minor ⋮ Sufficient conditions for Hamiltonian graphs in terms of (signless Laplacian) spectral radius ⋮ The number of maximal cliques and spectral radius of graphs with certain forbidden subgraphs ⋮ Strong Turán stability ⋮ A Turán problem on digraphs avoiding distinct walks of a given length with the same endpoints ⋮ The signless Laplacian spectral radius of graphs with no intersecting triangles ⋮ The extremal \(\alpha \)-index of graphs with no 4-cycle and 5-cycle ⋮ A stability theorem for maximal \(K_{r+1}\)-free graphs ⋮ Spectral extrema of graphs with fixed size: cycles and complete bipartite graphs ⋮ The signless Laplacian spectral radius of \(2K_3\)-free graphs ⋮ A spectral Erdős-Rademacher theorem ⋮ Spectral Turán-type problems on cancellative hypergraphs ⋮ Maxima of the \(Q\)-index of leaf-free graphs with given size ⋮ Spectral extrema of graphs with fixed size: forbidden triangles and pentagons ⋮ On the spectral radius of graphs without a gem ⋮ Maxima of the Q ( L )-index of (minimally) 2-edge-connected graphs with given size ⋮ The high order spectral extremal results for graphs and their applications ⋮ Improving the Caro-Wei bound and applications to Turán stability ⋮ Turán-type problems on \([a, b\)-factors of graphs, and beyond] ⋮ The automorphism group of projective norm graphs ⋮ Spectral extremal results for hypergraphs ⋮ The sharp upper bounds on the \(A_{\alpha}\)-spectral radius of \(C_4\)-free graphs and Halin graphs ⋮ Powers of Hamiltonian cycles in multipartite graphs ⋮ The spectral radius of graphs without trees of diameter at most four ⋮ Eigenvalues and triangles in graphs ⋮ Spectral extrema of graphs: forbidden hexagon ⋮ The maximum spectral radius of non-bipartite graphs forbidding short odd cycles ⋮ Maxima of the \(Q\)-index: forbidden a Fan

This page was built for publication: Some new results in extremal graph theory