On the maximum number of odd cycles in graphs without smaller odd cycles

DOI10.1002/JGT.22738MaRDI QIDQ6056808zbMATHOpenAlexWikidataFDO

Authors A. Grzesik, Bartłomiej Kielak

Publication date 4 October 2023

Published in Journal of Graph Theory (Search for Journal in Brave)

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

zbMATH Keywords

extremal problemscyclescycle-free

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Enumeration in graph theory (05C30) Paths and cycles (05C38)

Abstract: We prove that for each odd integer $kgeq7$, every graph on $n$ vertices without odd cycles of length less than $k$ contains at most $(n/k{)}^k$ cycles of length $k$. This generalizes the previous results on the maximum number of pentagons in triangle-free graphs, conjectured by ErdH{o}s in 1984, and asymptotically determines the generalized Tur'an number $mathrmex(n,C_k,C_{k-2})$ for odd $k$. In contrary to the previous results on the pentagon case, our proof is not computer-assisted.

Recommendations

• scientific article; zbMATH DE number 3931048
• Extremal numbers for odd cycles
• Edge maximal non-bipartite graphs without odd cycles of prescribed lengths
• Graphs with large maximum degree containing no odd cycles of a given length
• Even cycles in graphs with many odd cycles

Cites work

• scientific article; zbMATH DE number 3869331 (Why is no real title available?)
• scientific article; zbMATH DE number 3041944 (Why is no real title available?)
• A bound on the inducibility of cycles
• A generalized Turán problem and its applications
• Cycles of length 5 in triangle-free graphs: a sporadic counterexample to a characterization of equality
• Extremal problems for cycles in graphs
• Generalized Turán problems for even cycles
• Many \(T\) copies in \(H\)-free graphs
• Maximum density of induced 5-cycle is achieved by an iterated blow-up of 5-cycle
• On 3-uniform hypergraphs without a cycle of a given length
• On the inducibility of cycles
• On the maximum number of five-cycles in a triangle-free graph
• On the number of \(C_ 5's\) in a triangle-free graph
• On the number of pentagons in triangle-free graphs
• On the structure of linear graphs
• Pentagons in triangle-free graphs
• Pentagons vs. triangles
• The history of degenerate (bipartite) extremal graph problems
• The inducibility of graphs
• The maximum number of triangles in \(C_{2k+1}\)-free graphs
• What we know and what we do not know about Turán numbers

Cited in

(19)

• On the maximum number of odd cycles in graphs without smaller odd cycles
• Graphs without short odd cycles are nearly bipartite
• On the independence numbers of the cubes of odd cycles
• Minimum number of edges that occur in odd cycles
• Stability version of Dirac's theorem and its applications for generalized Turán problems
• Extremal problems involving vertices and edges on odd cycles
• On the generalized Turán problem for odd cycles
• Extremal numbers for odd cycles
• Maximising the number of cycles in graphs with forbidden subgraphs
• scientific article; zbMATH DE number 4156480 (Why is no real title available?)
• Edge maximal non-bipartite graphs without odd cycles of prescribed lengths
• Multicolor Turán numbers. II: A generalization of the Ruzsa-Szemerédi theorem and new results on cliques and odd cycles
• scientific article; zbMATH DE number 151768 (Why is no real title available?)
• The maximum number of paths of length three in a planar graph
• scientific article; zbMATH DE number 3931048 (Why is no real title available?)
• scientific article; zbMATH DE number 951844 (Why is no real title available?)
• Graphs with large maximum degree containing no odd cycles of a given length
• scientific article; zbMATH DE number 7144824 (Why is no real title available?)
• A Bound on the Number of Edges in Graphs Without an Even Cycle

This page was built for publication: On the maximum number of odd cycles in graphs without smaller odd cycles

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