On the Hamiltonian Number of a Plane Graph

Lewis, Thomas M.

Discussiones Mathematicae. Graph Theory, Tome 39 (2019) no. 1, pp. 171-181.

Résumé

The Hamiltonian number of a connected graph is the minimum of the lengths of the closed spanning walks in the graph. In 1968, Grinberg published a necessary condition for the existence of a Hamiltonian cycle in a plane graph, formulated in terms of the degrees of its faces. We show how Grinberg’s theorem can be adapted to provide a lower bound on the Hamiltonian number of a plane graph.

Détail

Keywords: Hamiltonian cycle, Hamiltonian walk, Hamiltonian number, Hamiltonian spectrum, Grinberg’s theorem, planar graph

Bibliographie

[1] M. Araya and G. Wiener, On cubic planar hypohamiltonian and hypotraceable graphs, Electron. J. Combin. 18 (2011) #P85.

[2] T. Asano, T. Nishizeki and T. Watanabe, An upper bound on the length of a Hamil- tonian walk of a maximal planar graph, J. Graph Theory 4 (1980) 315-336. doi: 10.1002/jgt.3190040310

[3] J.-C. Bermond, On Hamiltonian walks, in: Proceedings of the Fifth British Combinatorial Conference, Util. Math., Winnipeg, Man. (1975) 41-51.

[4] J.A. Bondy and U.S.R. Murty, Graph Theory (Springer, New York, 2008).

[5] G.J. Chang, T.-D. Chang and L.-D. Tong, Hamiltonian numbers of M¨obius double loop networks, J. Comb. Optim. 23 (2012) 462-470. doi: 10.1007/s10878-010-9360-4

[6] T.-D. Chang and L.-D. Tong, The Hamiltonian numbers in digraphs, J. Combin. Optim. 25 (2013) 694-701. doi: 10.1007/s10878-012-9512-9

[7] G. Chartrand and P. Zhang, A First Course in Graph Theory (Dover Publications, Incorporated, 2012).

[8] G. Chartrand, T. Thomas, P. Zhang and V. Saenpholphat, A new look at Hamilto- nian walks, Bull. Inst. Combin. Appl. 42 (2004) 37-52. [9] S.E. Goodman and S.T. Hedetniemi, On Hamiltonian walks in graphs, SIAM J. Comput. 3 (1974) 214-221. doi: 10.1137/0203017

[9] S.E. Goodman, S.T. Hedetniemi and P.J. Slater, Advances on the Hamiltonian com- pletion problem, J. Association Computing Machinery 22 (1975) 352-360. doi: 10.1145/321892.321897

[10] E. Grinberg, Plane homogeneous graphs of degree three without Hamiltonian circuits, Latvian Math. Yearbook 4, Izdat. “Zinatne”, Riga (1968) 51-58, in Russian.

[11] D. Král, L.-D. Tong and X. Zhu, Upper Hamiltonian numbers and Hamiltonian spectra of graphs, Australas. J. Combin. 35 (2006) 329-340.

[12] D. Liu, Hamiltonian spectra of trees, Ars Combin. 99 (2011) 415-419.

[13] T. Nishizeki, T. Asano and T.Watanabe, An approximation algorithm for the Hamil- tonian walk problem on maximal planar graphs, Discrete Appl. Math. 5 (1983) 211-222. doi: 10.1016/0166-218X(83)90042-2

[14] F. Okamoto, P. Zhang and V. Saenpholphat, The upper traceable number of a graph, Czechoslovak Math. J. 58 (2008) 271-287. doi: 10.1007/s10587-008-0016-9

[15] N. Punnim, V. Saenpholphat and S. Thaithae, Almost Hamiltonian cubic graphs, Internat. J. Comput. Sci. Inform. Security 7 (2007) 83-86.

[16] N. Punnim and S. Thaithae, The Hamiltonian number of some classes of cubic graphs, East-West J. Math. 12 (2010) 17-26.

[17] V. Saenpholphat, F. Okamoto and P. Zhang, Measures of traceability in graphs, Math. Bohem. 131 (2006) 63-83.

[18] S. Thaithae and N. Punnim, The Hamiltonian number of cubic graphs, in: Computational Geometry and Graph Theory, Lecture Notes in Comput. Sci. 4535, H. Ito, M. Kano, N. Katoh and Y. Uno (Ed(s)), (Springer, Berlin, Heidelberg, 2008) 213-223. doi: 10.1007/978-3-540-89550-3 23

[19] P. Vacek, On open Hamiltonian walks in graphs, Arch. Math. (Brno) 27A (1991) 105-111.

[20] P. Vacek, Bounds of lengths of open Hamiltonian walks, Arch. Math. (Brno) 28 (1992) 11-16.

[21] G. Wiener and M. Araya, On planar hypohamiltonian graphs, J. Graph Theory 67 (2011) 55-68. doi: 10.1002/jgt.20513.