×

On the Hamiltonian number of a plane graph. (English) Zbl 1401.05085

Summary: The Hamiltonian number of a connected graph is the minimum of the lengths of the closed spanning walks in the graph. E. Grinberg [“Plane homogeneous graphs of degree three without Hamiltonian circuits”, Latvian Math. Ann. 4, 51–58 (1968)] 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.

MSC:

05C10 Planar graphs; geometric and topological aspects of graph theory
05C45 Eulerian and Hamiltonian graphs
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] M. Araya and G. Wiener, On cubic planar hypohamiltonian and hypotraceable graphs, Electron. J. Combin. 18 (2011) #P85. · Zbl 1217.05065
[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: · Zbl 0433.05037
[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: · Zbl 1245.90131
[6] T.-D. Chang and L.-D. Tong, The Hamiltonian numbers in digraphs, J. Combin. Optim. 25 (2013) 694-701. doi: · Zbl 1291.90276
[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:
[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: · Zbl 0307.05123
[10] E. Grinberg, Plane homogeneous graphs of degree three without Hamiltonian circuits, Latvian Math. Yearbook 4, Izdat. “Zinatne”, Riga (1968) 51-58, in Russian. · Zbl 0185.27901
[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. · Zbl 1095.05023
[12] D. Liu, Hamiltonian spectra of trees, Ars Combin. 99 (2011) 415-419. · Zbl 1265.05194
[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: · Zbl 0511.05042
[14] F. Okamoto, P. Zhang and V. Saenpholphat, The upper traceable number of a graph, Czechoslovak Math. J. 58 (2008) 271-287. doi: · Zbl 1174.05040
[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. · Zbl 1238.05077
[17] V. Saenpholphat, F. Okamoto and P. Zhang, Measures of traceability in graphs, Math. Bohem. 131 (2006) 63-83. · Zbl 1112.05032
[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: · Zbl 1162.05332
[19] P. Vacek, On open Hamiltonian walks in graphs, Arch. Math. (Brno) 27A (1991) 105-111. · Zbl 0758.05067
[20] P. Vacek, Bounds of lengths of open Hamiltonian walks, Arch. Math. (Brno) 28 (1992) 11-16. · Zbl 0782.05056
[21] G. Wiener and M. Araya, On planar hypohamiltonian graphs, J. Graph Theory 67 (2011) 55-68. doi: · Zbl 1223.05168
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.