A cycle structure theorem for Hamiltonian graphs
type: Item
instance of: scholarly article
title: A cycle structure theorem for Hamiltonian graphs
zbMATH Open document ID: 0607.05050
DOI: 10.1016/0095-8956(88)90058-5
published in: Journal of Combinatorial Theory. Series B
publication date: 1988-01-01T00:00:00Z
review text: An n-vertex graph is called pancyclic if it contains a cycle of length \(\ell\) for every \(\ell\) such that \(3\leq \ell \leq n.\) We establish the following result: Let C be a hamiltonian cycle in an n- vertex graph G. Suppose C contains consecutive vertices x,y such that \(d(x)+d(y)\geq n\). Then G is either (i) pancyclic, (ii) bipartite, or (iii) missing only an (n-1)-cycle. Moreover, (iii) can only occur if G has a very explicit structure ''near'' x and y. This result can be used to show that three well-known hamiltonian degree conditions (due to Chvátal, Fan, and Bondy) actually imply that a graph is essentially pancyclic.
Mathematics Subject Classification ID: 05C45
Mathematics Subject Classification ID: 05C75
Mathematics Subject Classification ID: 05C38
zbMATH DE Number: 3981217
zbMATH Keywords: Hamiltonian cycle
zbMATH Keywords: Hamiltonian degree conditions
author: E. Schmeichel
author: S. Louis Hakimi
MaRDI profile type: Publication
full work available at URL: 0095-8956(88)90058-5
OpenAlex ID: W2985590381
cites work: Hamiltonian degree conditions which imply a graph is pancyclic
cites work: The Geng-Hua Fan conditions for pancyclic or Hamilton-connected graphs
cites work: Pancyclic graphs. I
cites work: Q3097395
cites work: On Hamilton's ideals
cites work: New sufficient conditions for cycles in graphs
cites work: On a conjecture of Bondy
cites work: Pancyclic graphs and a conjecture of Bondy and Chvatal
Recommended article: Another cycle structure theorem for Hamiltonian graphs
Recommended article: Q3385707
Recommended article: Q3481737
Recommended article: On the cyclic properties of Hamiltonian graphs
Recommended article: Q4294613
Recommended article: Q3363862
Recommended article: On the structure of the set of cycle lengths in a Hamiltonian graph
Recommended article: Hamiltonian cycles in n‐extendable graphs
Recommended article: Q3469119
Recommended article: On Hamilton cycles in certain planar graphs
description: scientific article; zbMATH DE number 3981217