Hamiltonian Number

The Hamiltonian number  of a connected graph  is the length of a Hamiltonian walk . In other words, it is the minimum length of a closed spanning walk in the graph. For a Hamiltonian graph, , where  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  is called an almost Hamiltonian graph.

Punnim et al. (2007) show that

(1)

with  iff  is a tree. Since a tree has Hamiltonian number , an almost Hamiltonian tree must satisfy , giving . Since the 3-path graph  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  is a -connected graph on  vertices with diameter , then

(2)

(Goodman and Hedetniemi 1974, Lewis 2019).

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

(3)

(Punnim et al. 2007).

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

graph
-barbell graph
complete k-partite graph
generalized Petersen graph
Hamiltonian graph
-kayak paddle graph
-lollipop graph
-tadpole graph
tree

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.