Hamiltonian Spectra of Graphs

A hamiltonian walk in a digraph D is a closed spanning directed walk of D with minimum length. The length of a hamiltonian walk in D is called the hamiltonian number of D, and is denoted by h(D). The hamiltonian spectrum Sh(G) of a graph G is the set {h(D):D is a strongly connected orientation of G}. In this paper, we present necessary and sufficient conditions for a graph G of order n to have Sh(G)={n}, {n+1}, or {n+2}. Then we construct some 2-connected graphs of order n with hamiltonian spectrum being a singleton n+k for some k3, and graphs with their hamiltonian spectra being sets of consecutive integers.