Article

Distributing Vertices on Hamiltonian Cycles

Journal of Graph Theory
Document Type

Article
Publication Date

1-1-2012
DOI

10.1002/jgt.20564
Disciplines

Abstract

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/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 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

Available at: http://works.bepress.com/colton_magnant/26/