k-Ordered Hamiltonian Graphs

Published

Journal Article

A hamiltonian graph G of order n is k-ordered, 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. Theorems by Dirac and Ore, presenting sufficient conditions for a graph to be hamiltonian, are generalized to k-ordered hamiltonian graphs. The existence of k-ordered graphs with small maximum degree is investigated; in particular, a family of 4-regular 4-ordered graphs is described. A graph G of order n ≥ 3 is k-hamiltonian-connected, 2 ≤ k ≤ n, if for every sequence v1, v2, . . . , vk of k distinct vertices, G contains a v1-vk hamiltonian path that encounters v1, v2, . . . , vk in this order. It is shown that for k ≥ 3, every (k + 1)-hamiltonian-connected graph is k-ordered and a result of Ore on hamiltonian-connected graphs is generalized to k-hamiltonian-connected graphs. © 1997 John Wiley & Sons, Inc.

Full Text

Duke Authors

Cited Authors

  • Ng, L; Schultz, M

Published Date

  • January 1, 1997

Published In

Volume / Issue

  • 24 / 1

Start / End Page

  • 45 - 57

International Standard Serial Number (ISSN)

  • 0364-9024

Digital Object Identifier (DOI)

  • 10.1002/(SICI)1097-0118(199701)24:1<45::AID-JGT6>3.0.CO;2-J

Citation Source

  • Scopus