The Hamiltonian Numbers in Graphs

Abstract

A Hamiltonian walk of a connected graph $G$ is a closed spanning walk of minimum length in $G$. The length of a Hamiltonian walk in $G$ is called the Hamiltonian number, denoted by $h(G)$. An Eulerian walk of a connected graph $G$ is a closed walk of minimum length which contains all edges of $G$. In this paper, we improve some results in [5] and give a necessary and sufficient condition for $h(G)<e(G)$. Then we prove that if two nonadjacent vertices $u$ and $v$ satisfying that $\mathrm{deg}(u)+\mathrm{deg}(v)\ge |V(G)|$, then $h(G)=h(G+uv)$. This result generalizes a theorem of Bondy and Chvatal for the Hamiltonian property. Finally, we show that if $0\le k\le n-2$ and $G$ is a 2-connected graph of order $n$ satisfying $\mathrm{deg}(u)+\mathrm{deg}(v)+\mathrm{deg}(w)\ge \frac{3n+k-2}{2}$ for every independent set $\{u,v,w\}$ of three vertices in $G$, then $h(G)\le n+k$. It is a generalization of Bondy's result.