Distributing vertices on Hamiltonian cycles

Let G be a graph of order n and 3≤ t ≤ n /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 /2 t . 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 X ⊆ V ( 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 . © 2011 Wiley Periodicals, Inc. J Graph Theory 69: 28–45, 2012