Distributing Vertices on Hamiltonian CyclesJournal of Graph Theory
AbstractLet 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/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 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.
Citation InformationRalph 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
Available at: http://works.bepress.com/colton_magnant/26/