Hostname: page-component-7b7567c8c-7pwfn Total loading time: 0 Render date: 2026-11-16T14:01:41.072Z Has data issue: false hasContentIssue false

Longest Cycles in 3-Connected 3-Regular Graphs

Published online by Cambridge University Press:  20 November 2018

J. A. Bondy
Affiliation:
University of Waterloo, Waterloo, Ontario
M. Simonovits
Affiliation:
Eötvös Loránd University, Budapest, Hungary
Rights & Permissions [Opens in a new window]

Extract

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.

In this paper, we study the following question: How long a cycle must there be in a 3-connected 3-regular graph on n vertices? For planar graphs this question goes back to Tait [6], who conjectured that any planar 3-connected 3-regular graph is hamiltonian. Tutte [7] disproved this conjecture by finding a counterexample on 46 vertices. Using Tutte's example, Grunbaum and Motzkin [3] constructed an infinite family of 3-connected 3-regular planar graphs such that the length of a longest cycle in each member of the family is at most nc, where c = 1 – 2–17 and n is the number of vertices. The exponent c was subsequently reduced by Walther [8, 9] and by Grùnbaum and Walther [4].

Information

Type
Research Article
Copyright
Copyright © Canadian Mathematical Society 1980