Premium
Distributing vertices on Hamiltonian cycles
Author(s) -
Faudree Ralph J.,
Gould Ronald J.,
Jacobson Michael S.,
Magnant Colton
Publication year - 2012
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20564
Subject(s) - combinatorics , mathematics , wheel graph , hamiltonian path , hamiltonian (control theory) , graph , path graph , bound graph , quartic graph , discrete mathematics , graph power , line graph , mathematical optimization
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