A cycle structure theorem for Hamiltonian graphs
From MaRDI portal
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.
Recommendations
- Another cycle structure theorem for Hamiltonian graphs
- A new cycle structure theorem for Hamiltonian graphs
- scientific article; zbMATH DE number 4152419
- On the cyclic properties of Hamiltonian graphs
- scientific article; zbMATH DE number 568821
- On cyclic properties of some Hamiltonian graphs
- On the structure of the set of cycle lengths in a Hamiltonian graph
- Hamiltonian cycles in n‐extendable graphs
- Publication:3469119
- On Hamilton cycles in certain planar graphs
Cites work
- Graph theory with applications
- Hamiltonian degree conditions which imply a graph is pancyclic
- New sufficient conditions for cycles in graphs
- On a conjecture of Bondy
- On Hamilton's ideals
- Pancyclic graphs and a conjecture of Bondy and Chvatal
- Pancyclic graphs. I
- The Geng-Hua Fan conditions for pancyclic or Hamilton-connected graphs
Cited in
(57)- Removable matchings and Hamiltonian cycles
- Dirac's type sufficient conditions for hamiltonicity and pancyclicity
- A condition for a Hamiltonian bipartite graph to be bipancyclic
- Another cycle structure theorem for Hamiltonian graphs
- Locally pancyclic graphs
- Pancyclism and bipancyclism of Hamiltonian graphs
- A degree characterisation of pancyclicity
- The diameters of some transition graphs constructed from Hamilton cycles
- On pancyclism in Hamiltonian graphs
- A generalization of Fan's condition for Hamiltonicity, pancyclicity, and Hamiltonian connectedness
- Cycles in Hamiltonian graphs of prescribed maximum degree
- On the structure of the set of cycle lengths in a Hamiltonian graph
- Thin Hamiltonian cycles on Archimedean graphs
- Hamiltonian degree conditions for tough graphs
- Hamilton cycles in some vertex-transitive graphs
- Hamilton-connected, vertex-pancyclic and bipartite holes
- Pancyclism and small cycles in graphs
- An evidence for Lovász conjecture about Hamiltonian paths and cycles
- On cyclic properties of some Hamiltonian graphs
- A new cycle structure theorem for Hamiltonian graphs
- Cycles in graphs and related problems
- On the cycle spectrum of cubic Hamiltonian graphs
- An implicit degree condition for pancyclicity of graphs
- scientific article; zbMATH DE number 3983207 (Why is no real title available?)
- An implicit degree Ore-condition for pancyclicity of graphs
- Generalizations of Dirac's theorem in Hamiltonian graph theory -- a survey
- scientific article; zbMATH DE number 1187330 (Why is no real title available?)
- Estimates on the size of the cycle spectra of Hamiltonian graphs
- Hamiltonicity, independence number, and pancyclicity
- Cycle spectra of Hamiltonian graphs
- Fan's condition on induced subgraphs for circumference and pancyclicity
- A short proof of a theorem on Hamiltonian graphs
- scientific article; zbMATH DE number 1409190 (Why is no real title available?)
- Cycle Extendability of Hamiltonian Strongly Chordal Graphs
- Low independence number and Hamiltonicity implies pancyclicity
- Cycles of many lengths in Hamiltonian graphs
- A triple of heavy subgraphs ensuring pancyclicity of 2-connected graphs
- A Fan-type heavy triple of subgraphs for pancyclicity of 2-connected graphs
- New sufficient conditions for hamiltonian and pancyclic graphs
- Flows in circulant graphs of odd order are sums of Hamilton cycles
- The cycle spectrum of claw-free Hamiltonian graphs
- Cycle lengths in Hamiltonian graphs with a pair of vertices having large degree sum
- Combinatorics, probability and computing. Abstracts from the workshop held April 24--30, 2022
- Chvátal-Erdős condition for pancyclicity
- A note on Frucht diagrams, Boolean graphs and Hamilton cycles
- Applying a condition for a Hamiltonian bipartite graph to be bipancyclic
- A generalization of Bondy's pancyclicity theorem
- Chvátal-Erdős condition for pancyclicity (extended abstract)
- A generalization of Bondy's pancyclicity theorem (extended abstract)
- On the pancyclicity of 2-connected \([5, 3]\)-graphs
- Pancyclicity of Hamiltonian graphs
- The Hamiltonicity and pancyclicity of split graphs
- Degree sum condition for chorded pancyclicity of claw-free graphs
- A new sufficient condition for pancyclability of graphs
- Cycle lengths of Hamiltonian \(P_\ell\)-free graphs
- A Fan-type heavy pair of subgraphs for pancyclicity of 2-connected graphs
- Hamiltonian degree conditions which imply a graph is pancyclic
This page was built for publication: A cycle structure theorem for Hamiltonian graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1085183)
