pith. machine review for the scientific record. sign in

arxiv: 1104.3334 · v2 · submitted 2011-04-17 · 🧮 math.CO

Recognition: unknown

Hamiltonicity, independence number, and pancyclicity

Authors on Pith no claims yet
classification 🧮 math.CO
keywords graphindependencenumberpancyclicpancyclicitythenverticesalready
0
0 comments X
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.