A graph G of order n is k-ordered hamiltonian, 2 ≤ k ≤ n, if for every sequence v1, v2, ..., vk of k distinct vertices of G, there exists a hamiltonian cycle that encounters v1, v2, ..., vk in this order. In this paper, we generalize two well-known theorems of Chartrand on hamiltonicity of iterated line graphs to k-ordered hamiltonicity. We prove that if Ln (G) is k-ordered hamiltonian and n is sufficiently large, then Ln + 1 (G) is (k + 1)-ordered hamiltonian. Furthermore, for any connected graph G, which is not a path, cycle, or the claw K1, 3, there exists an integer N′ such that LN′ + (k - 3) (G) is k-ordered hamiltonian for k ≥ 3.
|Number of pages||7|
|State||Published - Apr 6 2009|
Bibliographical noteFunding Information:
This research was performed at the University of Minnesota Duluth under the supervision of Joseph A. Gallian. It was funded by NSF grant DMS 9820179 and NSA grant MDA 904-00-10026. The authors wish to thank Mike Develin and Dan Isaksen for many useful suggestions. The authors also thank the referees for their careful reading of the paper and helpful suggestions which helped to improve the proof.
- Iterated line graph
- k-ordered hamiltonian
ASJC Scopus subject areas
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics