On the circumferences of regular 2-connected graphs

Let G be a 2-connected d-regular graph on rz less than or equal to rd (r gr eater than or equal to 3) vertices and c(G) denote the circumference of G. Bendy conjectured that c(G) greater than or equal to 2n/(r - 1) if n is lar ge enough. In this paper, we show that c(G) greater than or equal to 2n/(r - 1) + 2(r - 3)/(r - 1) For any integer r greater than or equal to 3. In pa rticular, G is hamiltonian if r = 3. This generalizes a result of Jackson. Examples to show that the bond for c(G) is sharp and that Bendy's conjectur e does not hold if r is allowed to take non-integer values are given. (C) 1 999 Academic Press.