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 \(\deg(u) + \deg(v) \geq |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 \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.