Cycle lengths in sparse graphs
From MaRDI portal
Publication:949802
DOI10.1007/S00493-008-2300-6zbMATH Open1174.05065DBLPjournals/combinatorica/SudakovV08arXiv0707.2117OpenAlexW2143169901WikidataQ56227676 ScholiaQ56227676MaRDI QIDQ949802FDOQ949802
Authors: Benny Sudakov, J. Verstraëte 
Publication date: 21 October 2008
Published in: Combinatorica (Search for Journal in Brave)
Abstract: Let C(G) denote the set of lengths of cycles in a graph G. In the first part of this paper, we study the minimum possible value of |C(G)| over all graphs G of average degree d and girth g. Erdos conjectured that |C(G)| =Omega(d^{lfloor (g-1)/2
floor}) for all such graphs, and we prove this conjecture. In particular, the longest cycle in a graph of average degree d and girth g has length Omega(d^{lfloor (g-1)/2
floor}). The study of this problem was initiated by Ore in 1967 and our result improves all previously known lower bounds on the length of the longest cycle. Moreover, our bound cannot be improved in general, since known constructions of d-regular Moore Graphs of girth g have roughly that many vertices. We also show that Omega(d^{lfloor (g-1)/2
floor}) is a lower bound for the number of odd cycle lengths in a graph of chromatic number d and girth g. Further results are obtained for the number of cycle lengths in H-free graphs of average degree d. In the second part of the paper, motivated by the conjecture of Erdos and Gyarfas that every graph of minimum degree at least three contains a cycle of length a power of two, we prove a general theorem which gives an upper bound on the average degree of an n-vertex graph with no cycle of even length in a prescribed infinite sequence of integers. For many sequences, including the powers of two, our theorem gives the upper bound e^{O(log^* n)} on the average degree of graph of order n with no cycle of length in the sequence, where log^* n is the number of times the binary logarithm must be applied to n to get a number which is at most
Full work available at URL: https://arxiv.org/abs/0707.2117
Recommendations
- Cycle lengths in sparse random graphs
- On the sum of the reciprocals of cycle lengths in sparse graphs
- Approximating the Longest Cycle Problem in Sparse Graphs
- Cycle lengths in graphs with large minimum degree
- scientific article; zbMATH DE number 3916307
- On the distribution of cycle lengths in graphs
- Cycles of given lengths in unicyclic components in sparse random graphs
- A note on cycle lengths in graphs
- Cycle lengths and minimum degree of graphs
- Longest cycles in sparse random digraphs
Cites Work
- Pancyclic graphs. I
- Ramanujan graphs
- Norm-graphs and bipartite Turán numbers
- On a problem of K. Zarankiewicz
- Cycles of even length in graphs
- Title not available (Why is that?)
- Norm-graphs: Variations and applications
- On arithmetic progressions of cycle lengths in graphs
- Hamiltonian circuits in random graphs
- Explicit group-theoretical constructions of combinatorial schemes and their application to the design of expanders and concentrators
- Graphs with \(k\) odd cycle lengths
- Weakly pancyclic graphs
- Turán Numbers of Bipartite Graphs and Related Ramsey-Type Questions
- Title not available (Why is that?)
- On a graph theorem by dirac
- The number of cycle lengths in graphs of given minimum degree and girth
- A note on cycle lengths in graphs
- Title not available (Why is that?)
- Distribution of cycle lengths in graphs
- Cycles Modulo k
- On the distribution of cycle lengths in graphs
- Circumference and girth
- SOME OF MY FAVORITE SOLVED AND UNSOLVED PROBLEMS IN GRAPH THEORY
Cited In (41)
- Gaps in the cycle spectrum of 3-connected cubic planar graphs
- Long paths and cycles in random subgraphs of \(\mathcal{H}\)-free graphs
- Cycle lengths modulo \(k\) in expanders
- Cycles in triangle-free graphs of large chromatic number
- The number of shortest cycles and the chromatic uniqueness of a graph
- Distribution of cycle lengths in graphs
- Hamilton cycles in highly connected and expanding graphs
- Pancyclicity of Hamiltonian and highly connected graphs
- Circumference, chromatic number and online coloring
- A randomized embedding algorithm for trees
- Unavoidable cycle lengths in graphs
- Title not available (Why is that?)
- Cycle factors in dense graphs
- A Lower Bound on Cycle-Finding in Sparse Digraphs
- On the distribution of cycle lengths in graphs
- Cycle length parities and the chromatic number
- Generalized Turán problems for even cycles
- Generalized Turán problems for even cycles
- The automorphism group of projective norm graphs
- Cycles in graphs with small density
- Cycles of many lengths in Hamiltonian graphs
- Approximating the Longest Cycle Problem in Sparse Graphs
- Cycle lengths in expanding graphs
- On a conjecture of Bondy and Vince
- Linear cycles of consecutive lengths
- Listing all fixed-length simple cycles in sparse graphs in optimal time
- A Strengthening on Odd Cycles in Graphs of Given Chromatic Number
- On the spectra of large sparse graphs with cycles
- Cycle spectra of Hamiltonian graphs
- Cycles of Given Size in a Dense Graph
- The extremal function for cycles of length \(\ell\) mod \(k\)
- On some cycles in Wenger graphs
- Subdivisions of a large clique in \(C_6\)-free graphs
- Cycle lengths and minimum degree of graphs
- Cycles in graphs of fixed girth with large size
- A solution to Erdős and Hajnal’s odd cycle problem
- Cycle Lengths Modulo k in Large 3-connected Cubic Graphs, Advances in Combinatorics
- On 2-power unicyclic cubic graphs
- Cycles with consecutive odd lengths
- Cycles of given lengths in hypergraphs
- On the sum of the reciprocals of cycle lengths in sparse graphs
This page was built for publication: Cycle lengths in sparse graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q949802)
