Pancyclicity of Hamiltonian and highly connected graphs (Q974472): Difference between revisions
From MaRDI portal
Latest revision as of 21:59, 2 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Pancyclicity of Hamiltonian and highly connected graphs |
scientific article |
Statements
Pancyclicity of Hamiltonian and highly connected graphs (English)
0 references
3 June 2010
0 references
Let be \(\kappa (G)\) the vertex connectivity and \(\alpha (G)\) the independence number of \(G\). The authors prove that if \(\kappa(G) \geqslant 600\alpha(G)\) then \(G\) is pancyclic (i.e., contains cycles of length \(\ell\), \(3 \leqslant \ell \leqslant V(G)\)). This establishes a conjecture of \textit{B. Jackson} and \textit{O. Ordaz} [Discrete Math. 84, No.\,3, 241--254 (1990; Zbl 0726.05043)] up to a constant factor.
0 references
pancyclic
0 references
Hamiltonian graphs
0 references