The hamiltonian number of cubic graphs

Abstract

A Hamiltonian walk in a connected graph G of order n is a closed spanning walk of minimum length in G. The Hamiltonian number h(G) of a connected graph G is the length of a Hamiltonian walk in G. Thus h may be considered as a measure of how far a given graph is from being Hamiltonian. We prove that if G runs over the set of connected cubic graphs of order n and n ≠ 14then the values h(G) completely cover a line segment [a,b] of positive integers. For an even integer n ≥ 4, let C(3n) be the set of all connected cubic graphs of order n. We define min(h,3n = min{h(G): G ∈ C(3n)} and max(h, 3n = max{h(G):G ∈ C(3n)}. Thus for an even integer n ≥ 4, the two invariants min (h, 3n ) and max (h,3 n ) naturally arise. Evidently, min (h, 3n ) = n. The exact values of max (h, 3n ) are obtained in all situations. © 2008 Springer Berlin Heidelberg.