Cycle lengths in sparse graphs
From MaRDI portal
Publication:949802
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
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
- scientific article; zbMATH DE number 487720 (Why is no real title available?)
- scientific article; zbMATH DE number 554066 (Why is no real title available?)
- scientific article; zbMATH DE number 1496607 (Why is no real title available?)
- A note on cycle lengths in graphs
- Circumference and girth
- Cycles Modulo k
- Cycles of even length in graphs
- Distribution of cycle lengths in graphs
- Explicit group-theoretical constructions of combinatorial schemes and their application to the design of expanders and concentrators
- Graphs with \(k\) odd cycle lengths
- Hamiltonian circuits in random graphs
- Norm-graphs and bipartite Turán numbers
- Norm-graphs: Variations and applications
- On a graph theorem by dirac
- On a problem of K. Zarankiewicz
- On arithmetic progressions of cycle lengths in graphs
- On the distribution of cycle lengths in graphs
- Pancyclic graphs. I
- Ramanujan graphs
- SOME OF MY FAVORITE SOLVED AND UNSOLVED PROBLEMS IN GRAPH THEORY
- The number of cycle lengths in graphs of given minimum degree and girth
- Turán Numbers of Bipartite Graphs and Related Ramsey-Type Questions
- Weakly pancyclic graphs
Cited in
(42)- Gaps in the cycle spectrum of 3-connected cubic planar graphs
- A strengthening on odd cycles in graphs of given chromatic number
- Long paths and cycles in random subgraphs of \(\mathcal{H}\)-free graphs
- Cycle lengths modulo \(k\) in expanders
- The number of shortest cycles and the chromatic uniqueness of a graph
- Cycles in triangle-free graphs of large chromatic number
- Hamilton cycles in highly connected and expanding graphs
- Distribution of cycle lengths in graphs
- Pancyclicity of Hamiltonian and highly connected graphs
- A randomized embedding algorithm for trees
- Circumference, chromatic number and online coloring
- Unavoidable cycle lengths in graphs
- Cycle lengths modulo \(k\) in large 3-connected cubic graphs
- Cycle factors in dense graphs
- A Lower Bound on Cycle-Finding in Sparse Digraphs
- Ramsey results for cycle spectra
- 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
- Cycle lengths in expanding graphs
- Approximating the Longest Cycle Problem in Sparse Graphs
- Cycles of many lengths in Hamiltonian graphs
- On a conjecture of Bondy and Vince
- Listing all fixed-length simple cycles in sparse graphs in optimal time
- Cycle spectra of Hamiltonian graphs
- Linear cycles of consecutive lengths
- Classes of cubic graphs containing cycles of integer-power lengths
- On the spectra of large sparse graphs with cycles
- Cycles of Given Size in a Dense Graph
- The extremal function for cycles of length \(\ell\) mod \(k\)
- On some cycles in Wenger graphs
- Cycles in graphs of fixed girth with large size
- Subdivisions of a large clique in \(C_6\)-free graphs
- Cycle lengths and minimum degree of graphs
- Cycles with consecutive odd lengths
- A solution to Erdős and Hajnal’s odd cycle problem
- Cycles of given lengths in hypergraphs
- On the sum of the reciprocals of cycle lengths in sparse graphs
- On 2-power unicyclic cubic 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)
