Department of Mathematics
 Search | Help | Login | pdf version | printable version

Math @ Duke





.......................

.......................


Publications [#243957] of Lenhard L. Ng

Papers Published

  1. Ng, L; Schultz, M, k-Ordered Hamiltonian Graphs, Journal of Graph Theory, vol. 24 no. 1 (January, 1997), pp. 45-57, WILEY [doi]
    (last updated on 2024/03/28)

    Abstract:
    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.

 

dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821

Mathematics Department
Duke University, Box 90320
Durham, NC 27708-0320