TOPICS
Search

Hamiltonian Number

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook

The Hamiltonian number h(G) of a connected graph G is the length of a Hamiltonian walk on 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.

The Hamiltonian number of a connected graph G on n>=3 vertices that is nonhamiltonian is n+1 (equivalently, G is almost Hamiltonian) iff G has a Hamiltonian path whose endpoints have a common neighbor.

If G is a connected bipartite graph with nonempty bipartition classes of sizes a and b, then its Hamiltonian number is even and

h(G)>=2max(a,b).
(1)

Since n=a+b is the vertex count of G, no closed spanning walk of length n+1 exists if n is even or if 2max(a,b)>n+1. Therefore, a bipartite almost Hamiltonian graph must satisfy |a-b|=1.

Punnim et al. (2007) show that

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

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)
(3)

(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
(4)

(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 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.Thaithae, S. and Punnim, N. "The Hamiltonian Number of Graphs with Prescribed Connectivity." Ars Combin. 90, 237-244, 2009.

Referenced on Wolfram|Alpha

Hamiltonian Number

Cite this as:

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

Subject classifications