k-ordered hamiltonicity of iterated line graphs

Stephen G. Hartke, Kathleen Ponto

Research output: Contribution to journalArticlepeer-review

2 Scopus citations

Abstract

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.

Original languageEnglish
Pages (from-to)1491-1497
Number of pages7
JournalDiscrete Mathematics
Volume309
Issue number6
DOIs
StatePublished - 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

Fingerprint

Dive into the research topics of 'k-ordered hamiltonicity of iterated line graphs'. Together they form a unique fingerprint.

Cite this