TOPICS
Search

Hamiltonian Walk


HamiltonianWalk

A Hamiltonian walk on a connected graph is a closed walk of minimal length which visits every vertex of a graph (and may visit vertices and edges multiple times). For example, a Hamiltonian walk on the above 3-pan graph is given by the vertex sequence 4, 3, 1, 2, 3, 4 and hence is of length 5.

The length of a Hamiltonian walk in a graph G is called the Hamiltonian number h(G). A Hamiltonian graph has h(G)=n, where n=|G| is the vertex count. A graph with h(G)=n+1 is said to be almost Hamiltonian.


See also

Almost Hamiltonian Graph, Hamiltonian Cycle, Hamiltonian Graph, k-Cyclic Graph, Walk

Explore with Wolfram|Alpha

References

Asano, T.; Nishizeki, T.; and Watanabe, T. "An Upper Bound on the Length of a Hamiltonian Walk of a Maximal Planar Graph." J. Graph Th. 4, 315-336, 1980.Asano, T.; Nishizeki, T.; and Watanabe, T. "An Approximation Algorithm for the Hamiltonian Walk Problem on Maximal Planar Graph." J. Discr. Appl. Math. 5, 211-222, 1983.Bermond, J. C. "On Hamiltonian Walks." Congr. Numer. 15, 41-51, 1976.Chartrand, G.; Thomas, T.; Saenpholphat, V.; and Zhang, P. "A New Look at Hamiltonian Walks." Bull. Inst. Combin. Appl. 42, 37-52, 2004.Goodman, S. E. and Hedetniemi, S. T. "On Hamiltonian Walks in Graphs." In Proceedings of the Fourth Southeastern Conference on Combinatorics, Graph Theory and Computing. Held at Florida Atlantic University, Boca Raton, Fla., March 5-8, 1973 (Ed. F. Hoffman, R. B. Levow, and R. S. D. Thomas). Winnipeg, Manitoba: Utilitas Mathematica, pp. 335-342, 1973.Goodman, S. E. and Hedetniemi, S. T. "On Hamiltonian Walks in Graphs." SIAM J. Comput. 3, 214-221, 1974.Punnim, N.; Saenpholphat, V.; and Thaithae, S. "Almost Hamiltonian Cubic Graphs." Int. J. Comput. Sci. Netw. Security 7, 83-86, 2007.Takamizawa, K.; Nishizeki, T.; and Saito, N. "An Algorithm for Finding a Short Closed Spanning Walk in a Graph." Networks 10, 249-263, 1980.Vacek, P. "On Open Hamiltonian Walks in Graphs." Arch. Math. (Brno) 27A, 105-111, 1991.

Cite this as:

Weisstein, Eric W. "Hamiltonian Walk." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/HamiltonianWalk.html

Subject classifications