Hamiltonicity, independence number, and pancyclicity

DOI10.1016/J.EJC.2011.11.002zbMATH Open1239.05106arXiv1104.3334OpenAlexW2041377007MaRDI QIDQ412232FDOQ412232

Authors: Choongbum Lee, Benny Sudakov 

Publication date: 4 May 2012

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

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.

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

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.

zbMATH Keywords

Hamilton cycle

Mathematics Subject Classification ID

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

Cites Work

• Pancyclic graphs. I
• A note on Hamiltonian circuits
• Pancyclicity of Hamiltonian and highly connected graphs
• 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

Cited In (7)

• Embedding cycles in finite planes
• Embedding Graphs into Larger Graphs: Results, Methods, and Problems
• Pancyclic subgraphs of random graphs
• Pancyclicity of Hamiltonian and highly connected 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)