The Hamiltonian number of graphs with prescribed connectivity

Abstract

A Hamiltonian walk in a connected graph G is a closed walk of minimum length which contains every vertex of G. The Hamiltonian number h(G) of a connected graph G is the length of a Hamiltonian walk in G. Let G(n) be the set of all connected graphs of order n, G(n, k = k) be the set of all graphs in G(n) having connectivity k = k, and h(n, k) = {h(G) : G ∈ G(n, k = k)}. We prove in this paper that for any pair of integers n and k with 1 ≤ k ≤ n - 1, there exist positive integers a := min(h; n, k) = min{h(G) : G ∈ G(n, k = k)} and b := max(h; n, k) = max{h(G) : G ∈ G(n, k = k)} such that h(n, k) = {x ∈ ℤ : a ≤ x ≤ b}. The values of min(h; n, k) and max(h; n, k) are obtained in all situations.