Pancyclism in Chvátal-Erdős' graphs (Q809093): Difference between revisions

Let G be a simple graph with stability number \(\alpha\) and connectivity k such that \(\alpha\leq k\). According to a theorem by Chvátal-Erdős, G has a Hamiltonian cycle. This paper gives results about cycles of other lengths for such G. For example: (1) If \(G\neq K_{k,k}\) and \(G\neq C_ 5\), then G has a \(C_{n-1}.\) (2) If \(G\not\cong C_ 5\), then G has a \(C_ 4.\) (3) If \(\alpha =3\) and if \(G\neq K_{3,3}\), G has cycles of any length between 4 and n. The authors conjecture that the conclusion of (3) holds more generally when \(\alpha\leq k\) and G is not bipartite.