Grinberg’s criterion. (English) Zbl 1400.05138

Summary: We generalize Grinberg’s Hamiltonicity criterion for planar graphs. To this end, we first prove a technical theorem for embedded graphs. As a special case of a corollary of this theorem we obtain Zaks’ extension of Grinberg’s criterion (which encompasses earlier work of K. R. Gehner [Networks 6, 131–138 (1976; Zbl 0354.05039)] and Y. Shimamoto [J. Comb. Theory, Ser. B 24, 169–180 (1978; Zbl 0395.05052)]), but the result also implies Grinberg’s formula in its original form in a much broader context. Further implications are a short proof for a slightly strengthened criterion of Lewis bounding the length of a shortest closed walk from below as well as a generalization of a theorem due to J. A. Bondy and R. Häggkvist [Aequationes Math. 22, 42–45 (1981; Zbl 0464.05037)].


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


[1] Berge, C., (Graphs and Hypergraphs, North-Holland Math. Library, vol. 6, (1973)) · Zbl 0254.05101
[2] Biggs, N. L.; Lloyd, E. K.; Wilson, R. J., Graph theory, 1736-1936, (1976), Clarendon Press Oxford · Zbl 0335.05101
[3] Bondy, J. A.; Häggkvist, R., Edge-disjoint Hamilton cycles in 4-regular planar graphs, Aequationes Math., 22, 42-45, (1981) · Zbl 0464.05037
[4] Bondy, J. A.; Murty, U. S.R., (Graph Theory, Graduate Texts in Mathematics, vol. 244, (2008), Springer) · Zbl 1134.05001
[5] Chia, G. L.; Thomassen, C., Grinberg’s criterion applied to some non-planar graphs, Ars Combin., 100, 3-7, (2011) · Zbl 1265.05342
[6] Gehner, K. R., A necessary condition for the existence of a circuit of any specified length, Networks, 6, 131-138, (1976) · Zbl 0354.05039
[7] Goodman, S. E.; Hedetniemi, S. T., On Hamiltonian walks in graphs, SIAM J. Comput., 3, 214-221, (1974) · Zbl 0269.05113
[8] Grinberg, E. J., Plane homogeneous graphs of degree three without Hamiltonian circuits, Latvian Math. Yearbook, 4, 51-58, (1968), (in Russian). English translation by D. Zeps available at: http://www.ltn.lv/ dainize/MathPages/Grinberg.eng.article.pdf · Zbl 0185.27901
[9] Holton, D. A.; McKay, B. D., The smallest non-Hamiltonian 3-connected cubic planar graphs have 38 vertices, J. Combin. Theory Ser. B, 45, 305-319, (1988) · Zbl 0607.05051
[10] Honsberger, R., Mathematical gems I, dolciani mathematical expositions no. 1, (1974), Mathematical Association of America
[11] Jooyandeh, M.; McKay, B. D.; Östergård, P. R.J.; Pettersson, V. H.; Zamfirescu, C. T., Planar Hypohamiltonian graphs on 40 vertices, J. Graph Theory, 84, 121-133, (2017) · Zbl 1356.05029
[12] Kirkman, T. P., Question 6610, solution by the proposer, Math. Quest. Solut. Educ. Times, 35, 112-116, (1881)
[13] T.M. Lewis, On the Hamiltonian number of a plane graph, Discuss. Math. Graph Theory (in press). http://dx.doi.org/10.7151/dmgt.2084arXiv:1508.06892; T.M. Lewis, On the Hamiltonian number of a plane graph, Discuss. Math. Graph Theory (in press). http://dx.doi.org/10.7151/dmgt.2084arXiv:1508.06892
[14] Mohar, B.; Thomassen, C., Graphs on surfaces, (2001), Johns Hopkins University Press Baltimore, MD · Zbl 0979.05002
[15] Sachs, H., Ein von kozyrev und grinberg angegebener nicht-hamiltonischer kubischer planarer graph. beiträge zur graphentheorie, 127-130, (1968), Teubner Leipzig, (in German) · Zbl 0169.26402
[16] Shimamoto, Y., On an extension of the grinberg theorem, J. Combin. Theory Ser. B, 24, 169-180, (1978) · Zbl 0395.05052
[17] Thomassen, C., Planar and infinite Hypohamiltonian and hypotraceable graphs, Discrete Math., 14, 4, 377-389, (1976) · Zbl 0322.05130
[18] Tutte, W. T., On Hamiltonian circuits, J. Lond. Math. Soc., 21, 98-101, (1946) · Zbl 0061.41306
[19] Tutte, W. T., Non-Hamiltonian planar maps, (Read, R., Graph Theory and Computing, (1972), Academic Press New York), 295-301 · Zbl 0247.05112
[20] West, D. B., Introduction to graph theory, (2001), Prentice Hall
[21] Wiener, G., New constructions of Hypohamiltonian and hypotraceable graphs, J. Graph Theory, 87, 526-535, (2018) · Zbl 1386.05102
[22] Zaks, J., Extending an extension of grinberg’s theorem, J. Combin. Theory Ser. B, 32, 95-98, (1982) · Zbl 0485.05036
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.