On the circumferences of regular 2-connected graphs (Q1306425): Difference between revisions

Let \(G\) be a 2-connected \(d\)-regular graph on \(n\leq rd\) \((r\geq 3)\) vertices and \(c(G)\) denote the circumference of \(G\). \textit{J. A. Bondy} [Congr. Numerantium 21, 3-28 (1978; Zbl 0406.05046)] conjectured that \(c(G)\geq 2n/(r- 1)\) if \(n\) is large enough. We show that \(c(G)\geq 2n/(r- 1)+ 2(r- 3)/(r- 1)\) for any integer \(r\geq 3\). In particular, \(G\) is Hamiltonian if \(r=3\). This generalizes a result of \textit{B. Jackson} [J. Comb. Theory, Ser. B 29, 27-46 (1980; Zbl 0377.05027)]. Examples to show that the bound for \(c(G)\) is sharp and that Bondy's conjecture does not hold if \(r\) is allowed to take non-integer values are given. \(\copyright\) Academic Press.