Skip to main content
Distributing Vertices on Hamiltonian Cycles
Journal of Graph Theory
  • Ralph J. Faudree, University of Memphis
  • Ronald Gould, Emory University
  • Michael S. Jacobson, University of Colorado at Denver
  • Colton Magnant, Georgia Southern University
Document Type
Publication Date

Let G be a graph of order n and 3≤tn/4 be an integer. Recently, Kaneko and Yoshimoto [J Combin Theory Ser B 81(1) (2001), 100–109] provided a sharp δ(G) condition such that for any set X of t vertices, G contains a hamiltonian cycle H so that the distance along H between any two vertices of X is at least n/2t. In this article, minimum degree and connectivity conditions are determined such that for any graph G of sufficiently large order n and for any set of t vertices XV(G), there is a hamiltonian cycle H so that the distance along H between any two consecutive vertices of X is approximately n/t. Furthermore, the minimum degree threshold is determined for the existence of a hamiltonian cycle H such that the vertices of X appear in a prescribed order at approximately predetermined distances along H.

Citation Information
Ralph J. Faudree, Ronald Gould, Michael S. Jacobson and Colton Magnant. "Distributing Vertices on Hamiltonian Cycles" Journal of Graph Theory Vol. 69 Iss. 1 (2012) p. 28 - 45 ISSN: 1097-0118
Available at: