
arXiv: 0903.4567
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 $3 \le \ell \le n$. Write $��(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 $��(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��tal and Erd��s says that $G$ is Hamiltonian if $��(G) \ge ��(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 $��(G) \ge 600��(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 $��(G) \ge 600��(G)$ then G is pancyclic. Improving an old result of Erd��s, we also show that G is pancyclic if it is Hamiltonian and $n \ge 150��(G)^3$. Our arguments use the following theorem of independent interest on cycle lengths in graphs: if $��(G) \ge 300��(G)$ then G contains a cycle of length $\ell$ for all $3 \le \ell \le ��(G)/81$.
15 pages, 1 figure
Eulerian and Hamiltonian graphs, pancyclic, Hamiltonian, Theoretical Computer Science, Pancyclic, 05C38, 05C45, Computational Theory and Mathematics, Cycles, Hamiltonian graphs, FOS: Mathematics, Discrete Mathematics and Combinatorics, Mathematics - Combinatorics, Combinatorics (math.CO), Graphs, Paths and cycles
Eulerian and Hamiltonian graphs, pancyclic, Hamiltonian, Theoretical Computer Science, Pancyclic, 05C38, 05C45, Computational Theory and Mathematics, Cycles, Hamiltonian graphs, FOS: Mathematics, Discrete Mathematics and Combinatorics, Mathematics - Combinatorics, Combinatorics (math.CO), Graphs, Paths and cycles
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 12 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Top 10% | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 10% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
