Recognition: unknown
Hamiltonicity, independence number, and pancyclicity
classification
🧮 math.CO
keywords
graphindependencenumberpancyclicpancyclicitythenverticesalready
read the original 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.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.