A New Look at Hamiltonian Walks

Abstract

Let G be a connected graph of order n. A Hamiltonian walk of G is a closed spanning walk of minimum length in G. For a cyclic ordering s : v1, v2 , • • , vn , = v1 of V (G), let d(s) = ∑n i= 1 d(vi, vi+ 1 ), where d(vi, vi+1) is the distance between vi and vi+.1 for 1 < i < n. Then the Hamiltonian number h(G) of G is defined as h(G) = min {d(s)} , where the minimum is taken over all cyclic orderings s of V(G). It is shown that h(G) is the length of a Hamiltonian walk in G. Thus h(G) = n if and only if G is a Hamiltonian graph. It is also shown that h(G) = 2n — 2 if and only if G is a tree. Moreover, for every pair n, k of integers with 3 < n < k < 2n — 2, there exists a connected graph G of order n having h(G) = k. The upper Hamiltonian number is defined as h+ (G) = max {d(s)} , where the maximum is taken over all cyclic orderings s of V(G). We show, for a connected graph G of order II > 3, that h(G) = (G) if and only if G = Kn or G = K11,1. We also study the upper Hamiltonian number of a tree and present bounds for the upper Hamiltonian number of a connected graph in terms of its order.