### Abstract

For a graph G and an integer k, denote by Vk the set {v ε V(G) | d(v) ≥ k}. Veldman proved that if G is a 2-connected graph of order n with n ≤ 3k - 2 and |Vk| ≤ k, then G has a cycle containing all vertices of Vk. It is shown that the upper bound k on |Vk| is close to best possible in general. For the special case k = δ(G), it is conjectured that the condition |Vk| ≤ k can be omitted. Using a variation of Woodall's Hopping Lemma, the conjecture is proved under the additional condition that n ≤ 2δ(G) + δ(G) + 1. This result is an almost-generalization of Jackson's Theorem that every 2-connected k-regular graph of order n with n ≤ 3k is hamiltonian. An alternative proof of an extension of Jackson's Theorem is also presented.

Original language | Undefined |
---|---|

Pages (from-to) | 373-385 |

Number of pages | 13 |

Journal | Journal of graph theory |

Volume | 17 |

Issue number | 17 |

DOIs | |

Publication status | Published - 1993 |

### Keywords

- METIS-140367
- IR-71002

## Cite this

Broersma, H. J., van den Heuvel, J. P. M., van den Heuvel, J., Jung, H. A., & Veldman, H. J. (1993). Cycles containing all vertices of maximum degree.

*Journal of graph theory*,*17*(17), 373-385. https://doi.org/10.1002/jgt.3190170311