Distributing vertices on Hamiltonian cycles |
| |
| Authors: | Ralph J Faudree Ronald J Gould Michael S Jacobson Colton Magnant |
| |
| Institution: | 1. Department of Mathematical Sciences, University of Memphis, Memphis, Tennessee 38152;2. Department of Mathematics and Computer Science, Emory University Atlanta, Georgia 30322;3. Department of Mathematics, University of Colorado Denver, Denver, Colorado 80217;4. Department of Mathematics, Lehigh University, Bethlehem, Pennsylvania 18015 |
| |
| 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. © 2011 Wiley Periodicals, Inc. J Graph Theory 69: 28–45, 2012 |
| |
| Keywords: | hamiltonian cycles distances |
|
|
