CYCLES CONTAINING ALL VERTICES OF MAXIMUM DEGREE

For a graph G and an integer k, denote by V(k) the set {v is-an-elemen t-of V(G) \ d(v) greater-than-or-equal-to k}. Veldman proved that if G is a 2-connected graph of order n with n less-than-or-equal-to 3k - 2 and \V(k)\ less-than-or-equal-to k, then G has a cycle containing all vertices of V(k). It is shown that the upper bound k on \V(k)\ is clo se to best possible in general. For the special case k = DELTA(G), it is conjectured that the condition \V(k)\ less-than-or-equal-to k can b e omitted. Using a variation of Woodall's Hopping Lemma, the conjectur e is proved under the additional condition that n less-than-or-equal-t o 2DELTA(G) + delta(G) + 1. This result is an almost-generalization of Jackson's Theorem that every 2-connected k-regular graph of order n w ith n less-than-or-equal-to 3k is hamiltonian. An alternative proof of an extension of Jackson's Theorem is also presented.