## Abstract

A graph G of order n is k-ordered hamiltonian, 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. 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 L^{n} (G) is k-ordered hamiltonian and n is sufficiently large, then L^{n + 1} (G) is (k + 1)-ordered hamiltonian. Furthermore, for any connected graph G, which is not a path, cycle, or the claw K_{1, 3}, there exists an integer N^{′} such that L^{N′ + (k - 3)} (G) is k-ordered hamiltonian for k ≥ 3.

Original language | English |
---|---|

Pages (from-to) | 1491-1497 |

Number of pages | 7 |

Journal | Discrete Mathematics |

Volume | 309 |

Issue number | 6 |

DOIs | |

State | Published - Apr 6 2009 |

### Bibliographical note

Funding 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.

## Keywords

- Iterated line graph
- k-ordered hamiltonian

## ASJC Scopus subject areas

- Theoretical Computer Science
- Discrete Mathematics and Combinatorics