Pancyclicity of Hamiltonian and highly connected graphs
| dc.creator | Keevash, Peter | |
| dc.creator | Sudakov, Benny | |
| dc.date | 2009-03-26 | |
| dc.date.accessioned | 2026-07-07T12:57:04Z | |
| dc.date.available | 2026-07-07T12:57:04Z | |
| dc.description | 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$. | |
| dc.description | 15 pages, 1 figure | |
| dc.identifier | https://arxiv.org/abs/0903.4567 | |
| dc.identifier | http://arxiv.org/abs/0903.4567 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/224798 | |
| dc.subject | Combinatorics | |
| dc.subject | 05C38, 05C45 | |
| dc.title | Pancyclicity of Hamiltonian and highly connected graphs | |
| dc.type | text |