## The Hamiltonian numbers in graphs.(English)Zbl 1363.05150

Summary: 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 [S. E. Goodman and S. T. Hedetniemi, SIAM J. Comput. 3, 214–221 (1974; Zbl 0269.05113)] and give a necessary and sufficient condition for $$h(G)<e(G)$$. Then we prove that if two nonadjacent vertices $$u$$ and $$v$$ satisfy $$\deg(u)+\deg(v)\geq |V(G)|$$, then $$h(G)=h(G+uv)$$. This result generalizes a theorem of Bondy and Chvátal for the Hamiltonian property. Finally, we show that if $$0\leq k\leq n-2$$ and $$G$$ is a 2-connected graph of order $$n$$ satisfying $$\deg(u)+\deg(v)+\deg(w)\geq \frac{3n-k-2}{2}$$ for every independent set $$\{u,v,w\}$$ of three vertices in $$G$$, then $$h(G)\leq n+k$$. It is a generalization of Bondy’s result.

### MSC:

 05C45 Eulerian and Hamiltonian graphs 05C38 Paths and cycles 05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)

### Keywords:

Hamiltonian number; Eulerian walk

Zbl 0269.05113