Hamiltonicity, independence number, and pancyclicity

DOI10.1016/J.EJC.2011.11.002MaRDI QIDQ412232zbMATH OpenOpenAlexFDO

Authors Choongbum Lee, Benny Sudakov

Publication date 4 May 2012

Published in European Journal of Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

Hamilton cycle

Mathematics Subject Classification ID

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

Abstract: A graph on n vertices is called pancyclic if it contains a cycle of length l for all 3 le l le n. In 1972, Erdos proved that if G is a Hamiltonian graph on n > 4k^4 vertices with independence number k, then G is pancyclic. He then suggested that n = Omega(k^2) should already be enough to guarantee pancyclicity. Improving on his and some other later results, we prove that there exists a constant c such that n > ck^{7/3} suffices.

Recommendations

• Low independence number and Hamiltonicity implies pancyclicity
• Pancyclicity of Hamiltonian and highly connected graphs
• A sufficient condition for pancyclism of Hamiltonian graphs
• A cycle structure theorem for Hamiltonian graphs
• On Hamiltonian and pancyclic graph.

Cites work

• scientific article; zbMATH DE number 3465354 (Why is no real title available?)
• A note on Hamiltonian circuits
• A note on pancyclism of highly connected graphs
• Chvátal-Erdős conditions for paths and cycles in graphs and digraphs. A survey
• Pancyclic graphs. I
• Pancyclicity of Hamiltonian and highly connected graphs
• Pancyclism in Chvátal-Erdős' graphs
• The Chvátal-Erdös condition for cycles in triangle-free graphs

Cited in

(7)

• Embedding cycles in finite planes
• Embedding Graphs into Larger Graphs: Results, Methods, and Problems
• Pancyclicity of Hamiltonian and highly connected graphs
• Pancyclic subgraphs of random graphs
• Combinatorics, probability and computing. Abstracts from the workshop held April 24--30, 2022
• Hamiltonian properties and the bipartite independence number
• Low independence number and Hamiltonicity implies pancyclicity

This page was built for publication: Hamiltonicity, independence number, and pancyclicity

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