Grinberg’s criterion. (English) Zbl 1400.05138

Brinkmann, Gunnar; Zamfirescu, Carol T.

Eur. J. Comb. 75, 32-42 (2019).

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)].

MSC:

05C45	Eulerian and Hamiltonian graphs
05C10	Planar graphs; geometric and topological aspects of graph theory

Keywords:

Grinberg’s Hamiltonicity criterion

Citations:

Zbl 0354.05039; Zbl 0395.05052; Zbl 0464.05037

References:

[1]	Berge, C., (Graphs and Hypergraphs, North-Holland Math. Library, vol. 6, (1973))
[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.2084, arXiv:1508.06892 [math.CO].
[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)
[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