# 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