Pancyclicity of Hamiltonian and highly connected graphs

DOI10.1016/J.JCTB.2010.02.001zbMATH Open1208.05071arXiv0903.4567OpenAlexW2169450198MaRDI QIDQ974472FDOQ974472

Peter Keevash, Benny Sudakov

Publication date: 3 June 2010

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Abstract: A graph G on n vertices is Hamiltonian if it contains a cycle of length n and pancyclic if it contains cycles of length $ell$ for all $3leelllen$. Write $alpha(G)$ for the independence number of $G$, i.e. the size of the largest subset of the vertex set that does not contain an edge, and $kappa(G)$ for the (vertex) connectivity, i.e. the size of the smallest subset of the vertex set that can be deleted to obtain a disconnected graph. A celebrated theorem of Chv'atal and ErdH{o}s says that $G$ is Hamiltonian if $kappa(G)gealpha(G)$. Moreover, Bondy suggested that almost any non-trivial conditions for Hamiltonicity of a graph should also imply pancyclicity. Motivated by this, we prove that if $kappa(G)ge600alpha(G)$ then G is pancyclic. This establishes a conjecture of Jackson and Ordaz up to a constant factor. Moreover, we obtain the more general result that if G is Hamiltonian with minimum degree $delta(G)ge600alpha(G)$ then G is pancyclic. Improving an old result of ErdH{o}s, we also show that G is pancyclic if it is Hamiltonian and $nge150alpha(G{)}^3$. Our arguments use the following theorem of independent interest on cycle lengths in graphs: if $delta(G)ge300alpha(G)$ then G contains a cycle of length $ell$ for all $3leellledelta(G)/81$.

Full work available at URL: https://arxiv.org/abs/0903.4567

zbMATH Keywords

Hamiltonian graphspancyclic

Mathematics Subject Classification ID

Eulerian and Hamiltonian graphs (05C45) Paths and cycles (05C38)

Cites Work

• Pancyclic graphs. I
• The probabilistic method. With an appendix on the life and work of Paul Erdős.
• Some Theorems on Abstract Graphs
• A note on Hamiltonian circuits
• On arithmetic progressions of cycle lengths in graphs
• On cycle—Complete graph ramsey numbers
• Advances on the Hamiltonian problem -- a survey
• Updating the hamiltonian problem—A survey
• Title not available (Why is that?)
• A note on pancyclism of highly connected graphs
• The Chvátal-Erdös condition for cycles in triangle-free graphs
• Chvátal-Erdős conditions for paths and cycles in graphs and digraphs. A survey
• Title not available (Why is that?)
• Pancyclism in Chvátal-Erdős' graphs
• Cycle lengths in sparse graphs
• A note on cycle lengths in graphs

Cited In (9)

• Embedding cycles in finite planes
• Hamiltonicity, independence number, and pancyclicity
• Embedding Graphs into Larger Graphs: Results, Methods, and Problems
• Multistage positional games
• Combinatorics, probability and computing. Abstracts from the workshop held April 24--30, 2022
• Chvátal-Erdős condition for pancyclicity
• Hamilton-connected, vertex-pancyclic and bipartite holes
• Cycle lengths in randomly perturbed graphs
• Cycles of many lengths in Hamiltonian graphs

   Recommendations

• Hamiltonicity, independence number, and pancyclicity 👍 👎
• Low independence number and Hamiltonicity implies pancyclicity 👍 👎
• A sufficient condition for pancyclism of Hamiltonian graphs 👍 👎
• Title not available (Why is that?) 👍 👎
• A new sufficient condition for pancyclic graphs 👍 👎

This page was built for publication: Pancyclicity of Hamiltonian and highly connected graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q974472)