Extremal numbers for odd cycles
From MaRDI portal
Abstract: We describe the C_{2k+1}-free graphs on n vertices with maximum number of edges. The extremal graphs are unique except for n = 3k-1, 3k, 4k-2, or 4k-1. The value of ex(n,C_{2k+1}) can be read out from the works of Bondy, Woodall, and Bollobas, but here we give a new streamlined proof. The complete determination of the extremal graphs is also new. We obtain that the bound for n_0(C_{2k+1}) is 4k in the classical theorem of Simonovits, from which the unique extremal graph is the bipartite Turan graph.
Recommendations
- scientific article; zbMATH DE number 3931048
- On the maximum number of odd cycles in graphs without smaller odd cycles
- Turán numbers of bipartite graphs plus an odd cycle
- Graphs with large maximum degree containing no odd cycles of a given length
- Edge maximal non-bipartite graphs without odd cycles of prescribed lengths
Cites work
- A note on Turán numbers for even wheels
- A sufficient condition for all short cycles
- Extremal graph problems with symmetrical extremal graphs. Additional chromatic conditions
- scientific article; zbMATH DE number 3652374 (Why is no real title available?)
- scientific article; zbMATH DE number 863492 (Why is no real title available?)
- Large cycles in graphs
- Maximal circuits of graphs. I
- On maximal paths and circuits of graphs
- On the theory of graphs
- Pancyclic graphs. I
- Path Ramsey numbers in multicolorings
- Sufficient Conditions for Circuits in Graphs†
- The history of degenerate (bipartite) extremal graph problems
Cited in
(53)- Extremal problems involving vertices and edges on odd cycles
- Unavoidable hypergraphs
- An Erdős-Gallai type theorem for vertex colored graphs
- A new upper bound on extremal number of even cycles
- A spectral condition for the existence of a pentagon in non-bipartite graphs
- On the Turán number of theta graphs
- The Turán number of the square of a path
- Extremal graphs for two vertex-disjoint copies of a clique
- Extremal graphs for odd-ballooning of paths and cycles
- Adjacency eigenvalues of graphs without short odd cycles
- A spectral condition for odd cycles in non-bipartite graphs
- The Turán number of disjoint copies of paths
- Large induced subgraphs with three repeated degrees
- Extremal graph for intersecting odd cycles
- scientific article; zbMATH DE number 3931048 (Why is no real title available?)
- Turán number of an induced complete bipartite graph plus an odd cycle
- A strengthening of the spectral chromatic critical edge theorem: Books and theta graphs
- Outerplanar Turán numbers of cycles and paths
- Turán numbers for disjoint paths
- On the maximum number of odd cycles in graphs without smaller odd cycles
- A stability theorem for maximal C2k+1 ${C}_{2k+1}$‐free graphs
- Forbidden theta graph, bounded spectral radius and size of non-bipartite graphs
- Maximizing the degree powers of graphs with fixed size
- Extremal results for \(C_3^-\)-free signed graphs
- A stability result for $C_{2k+1}$-free graphs
- Spectral extrema of graphs with fixed size: forbidden triangles and pentagons
- On the maximum number of odd cycles in graphs without smaller odd cycles
- Extremal graphs for the odd prism
- Spectral extremal problem on t copies of -cycles
- Turán number of two vertex-disjoint copies of cliques.
- Turán problem of signed graph for negative odd cycle
- On generalized Turán numbers of intersecting cliques
- Extremal graphs for the suspension of edge-critical graphs
- Spectral extremal problem of the p th power of cycles
- Note on two Kirchhoff index Turán problems
- Generalized Turán problems for disjoint even wheels, and for disjoint bowties
- A note on two cycles of consecutive even lengths in graphs
- Spectral extremal results on edge blow-up of graphs
- Spectral extremal problem for the odd prism
- A spectral Erdős-Faudree-Rousseau theorem
- Bounds on the resistance distance and Kirchhoff index of graphs
- On the spectral extremal problem of planar graphs
- Decomposition family and spectral extremal problems on non-bipartite graphs
- Long cycles and spectral radii in planar graphs
- Turán numbers for vertex-disjoint triangles and pentagons
- The signless Laplacian spectral radius of book-free graphs
- A strong structural stability of \(C_{2 k + 1}\)-free graphs
- Non-bipartite graphs without theta subgraphs
- Number of copies of \(C_4\) guarantees strong structural stability of graphs forbidding \(C_{2k+1}\)
- Turán number of books in non-bipartite graphs
- Cycle lengths in graphs of given minimum degree
- Spectral extrema of graphs: forbidden hexagon
- Triangle-free graphs with the maximum number of cycles
This page was built for publication: Extremal numbers for odd cycles
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5364245)
