Math @ Duke

Publications [#243957] of Lenhard L. Ng
Papers Published
 Ng, L; Schultz, M, kOrdered Hamiltonian Graphs,
Journal of Graph Theory, vol. 24 no. 1
(1997),
pp. 4557 [doi]
(last updated on 2018/10/17)
Abstract: A hamiltonian graph G of order n is kordered, 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 kordered hamiltonian graphs. The existence of kordered graphs with small maximum degree is investigated; in particular, a family of 4regular 4ordered graphs is described. A graph G of order n ≥ 3 is khamiltonianconnected, 2 ≤ k ≤ n, if for every sequence v1, v2, . . . , vk of k distinct vertices, G contains a v1vk hamiltonian path that encounters v1, v2, . . . , vk in this order. It is shown that for k ≥ 3, every (k + 1)hamiltonianconnected graph is kordered and a result of Ore on hamiltonianconnected graphs is generalized to khamiltonianconnected graphs. © 1997 John Wiley & Sons, Inc.


dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821
 
Mathematics Department
Duke University, Box 90320
Durham, NC 277080320

