TOPICS
Search

Hamiltonian Number

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook

The Hamiltonian number h(n) of a connected graph G is the length of a Hamiltonian walk G. In other words, it is the minimum length of a closed spanning walk in the graph. For a Hamiltonian graph, h(G)=|G|, where |G| is the vertex count. The Hamiltonian number therefore gives one measure of how far away a graph is from being Hamiltonian, and a graph with h(G)=n+1 is called an almost Hamiltonian graph.

Punnim et al. (2007) show that

n<=h(G)<=2n-2,
(1)

with h(G)=2n-2 iff G is a tree. Since a tree has Hamiltonian number 2n-2, an almost Hamiltonian tree must satisfy 2n-2=n+1, giving n=3. Since the 3-path graph P_3 is the only tree on three nodes, it is also the only almost Hamiltonian tree.

In general, determining the Hamiltonian number of a graph is difficult (Lewis 2019).

If G is a k-connected graph on n vertices with diameter d, then

h(G)<=2(n-1)-|_k/2_|(2d-2)
(2)

(Goodman and Hedetniemi 1974, Lewis 2019).

If G is an almost Hamiltonian cubic graph with n vertices, then the triangle-replaced graph G^* has Hamiltonian number

h(G^*)=3n+2
(3)

(Punnim et al. 2007).

Values for special classes of (non-Hamiltonian) graphs are summarized in the table below, where n denotes the vertex count of the graph

graph Gh(G)
n-barbell graph2(n+1)
complete k-partite graph K_(k_1,k_2,...,k_n){k_1+k_2+...k_n for n=1 or k_1+k_2+...+k_n>=max(k_1,...,k_n); 2max(k_1,...,k_n) otherwise
generalized Petersen graph GP(k,m){2k+1 for k=5 (mod 6) and m=2; 2k otherwise
Hamiltonian graphn
(k,m,l)-kayak paddle graphk+m+2l
(m,n)-lollipop graphm+2n
(m,n)-tadpole graphm+2n
tree2n-2

See also

Almost Hamiltonian Graph, Graph Circumference, Hamiltonian Graph, Hamiltonian Walk

Explore with Wolfram|Alpha

References

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.Lewis, T. M. "On the Hamiltonian Number of a Plane Graph." Disc. Math. Graph Th. 39, 171-181, 2019.Punnim, N.; Saenpholphat, V.; and Thaithae, S. "Almost Hamiltonian Cubic Graphs." Int. J. Comput. Sci. Netw. Security 7, 83-86, 2007.Punnim, N. and Thaithae, S. "The Hamiltonian Number of Some Classes of Cubic Graphs." East-West J. Math. 12, 17-26, 2010.Thaithae, S. and Punnim, N. "The Hamiltonian Number of Graphs with Prescribed Connectivity." Ars Combin. 90, 237-244, 2009.Thaithae, S. and Punnim, N. "The Hamiltonian Number of Cubic Graphs." In Computational geometry and graph theory: Revised selected papers from the International Conference (Kyoto CGGT 2007) held at Kyoto University, Kyoto, June 11-15, 2007 (Ed. H. Ito, M. Kano, N. Katoh and Y. Uno). Berlin: Springer, pp. 213-233, 2008.

Cite this as:

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

Subject classifications