We consider connected, locally connected graphs in which the maximum and minimum degrees differ by a t most one and do not exceed five. It is shown that if C is a nonhamiltonian cycle in such a graph G, then there exists a cycle C' in G such that V(C) C V(C7 and IV(C')l = (V(C)I + 1.
1. Introduction
A graph G of order p 2 3 has a pancyclic ordering if the vertices of G can be labeled u , , u2, . . . ,up so that C, C ({u~, u2, . . . , u,}), for 3
vertex of G lies on a triangle of G and every nonhamiltonian cycle of G is extendable.
The investigation of the extent to which known sufficient conditions for a graph to be hamiltonian imply the extendability of cycles in that graph was initiated in [2], where a number of results were obtained. Here we pursue this theme further by strengthening the following result: Kikust's Theorem 131. Let G be a connected, locally connected, 5-regular graph. Then G has a pancyclic ordering.
Examples of graphs that satisfy the hypotheses of Kikust's theorem include K6, all three 5-regular graphs of order eight, the composition C, ,[K,] [ 1, p. 221 [(see Figure l(a)], and the graph of the icosahedron-all of which exhibit a high degree of symmetry-and at the other extreme, graphs like that of Figure l(b), which have little or no symmetry.
Oberly and Sumner [4] proved that if G is a connected, locally connected nontrivial graph that does not contain K , , , as an induced subgraph, then G is hamiltonian and Hendry [2] showed that the same hypotheses imply that G is fully cycle extendable. The graphs K4 and z3 + C, show that the hypotheses of these results and those of Kikust's theorem are independent.