Hostname: page-component-74656f9884-c52kr Total loading time: 0 Render date: 2026-11-07T09:03:30.430Z Has data issue: false hasContentIssue false

On Arithmetic Progressions of Cycle Lengths in Graphs

Published online by Cambridge University Press:  03 November 2000

JACQUES VERSTRAËTE
Affiliation:
Department of Pure Mathematics and Mathematical Statistics, 16 Mill Lane, Cambridge CB2 1SB, England (e-mail: J.B.A.Verstraete@dpmms.cam.ac.uk)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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 4k 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)n1+1/k has a cycle of length 2k.

Information

Type
Research Article
Copyright
2000 Cambridge University Press