Distributing Vertices on Hamiltonian Cycles
by
Ron Gould
Emory University, Atlanta, GA 30322
Coauthors: Ralph Faudree, Michael Jacobson, and Colton Magnant.

Let G be a graph of order n and 3 ≤ t ≤ [n/4] be an integer. Recently, Kaneko and Yoshimoto provided a sharp d(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 paper, 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, we determine the d threshold for any t chosen vertices to be on a hamiltonian cycle H in a prescribed order, with approximately predetermined distances along H between consecutive chosen vertices.

Date received: March 28, 2008