Premium
On k ‐ordered Hamiltonian graphs
Author(s) -
Kierstead H. A.,
Sárközy G. N.,
Selkow S. M.
Publication year - 1999
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/(sici)1097-0118(199909)32:1<17::aid-jgt2>3.0.co;2-g
Subject(s) - combinatorics , mathematics , hamiltonian path , graph , hamiltonian (control theory) , discrete mathematics , mathematical optimization
A Hamiltonian graph G of order n is k ‐ordered, 2 ≤ k ≤ n , if for every sequence v 1 , v 2 , …, v k of k distinct vertices of G , there exists a Hamiltonian cycle that encounters v 1 , v 2 , …, v k in this order. Define f ( k, n ) as the smallest integer m for which any graph on n vertices with minimum degree at least m is a k ‐ordered Hamiltonian graph. In this article, answering a question of Ng and Schultz, we determine f ( k, n ) if n is sufficiently large in terms of k . Let g ( k, n ) = $\lceil{{n}\over{2}}\rceil + \lfloor{{k}\over{2}}\rfloor$ − 1. More precisely, we show that f ( k, n ) = g ( k, n ) if n ≥ 11 k − 3. Furthermore, we show that f ( k, n ) ≥ g ( k, n ) for any n ≥ 2 k . Finally we show that f ( k, n ) > g ( k, n ) if 2 k ≤ n ≤ 3 k − 6. © 1999 John Wiley & Sons, Inc. J Graph Theory 32: 17–25, 1999