Combinatorics Probability Computing · 2000 · 113 citations · 7 references
Natural SciencesComputer ScienceMathematicsAlgorithmsCombinatoricsNumber TheoryCombinatorial Number TheoryDirected Acyclic GraphsGraph AlgorithmsGraph Theory
A question recently posed by Häggkvist and Scott asked whether or not there exists a constant c such that, if G is a graph of minimum degree ck , then G contains cycles of k consecutive even lengths. In this paper we answer the question by proving that, for k > 2, a bipartite graph of average degree at least 4 k and girth g contains cycles of ( g /2 − 1) k consecutive even lengths. We also obtain a short proof of the theorem of Bondy and Simonovits, that a graph of order n and size at least 8( k − 1) n 1+1/ k has a cycle of length 2 k .
7
Cycles of even length in graphs
J. A. Bondy, Miklós Simonovits · Journal of Combinatorial Theory Series B · 1974 · 412 citations
Carsten Thomassen · Journal of Combinatorial Theory Series B · 1983 · 100 citations
Béla Bollobás · Bulletin of the London Mathematical Society · 1977 · 49 citations
Cycles in a graph whose lengths differ by one or two
J. A. Bondy, Andrew Vince · Journal of Graph Theory · 1998 · 33 citations