Skip to main content
Article
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
Article
Publication Date
1-1-2012
DOI
10.1002/jgt.20564
Disciplines
Abstract

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
Available at: http://works.bepress.com/colton_magnant/26/