The Hamiltonian numbers in graphs. (English) Zbl 1363.05150

Chang, Ting-Pang; Tong, Li-Da

Ars Comb. 123, 151-158 (2015).

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

Citations:

Zbl 0269.05113