zbMATH — the first resource for mathematics

Grinberg’s criterion applied to some non-planar graphs. (English) Zbl 1265.05342
Summary: G. N. Robertson [Graphs minimal under girth, valency and connectivity constraints, Ph.D. Thesis, Univ. of Waterloo, Ontario, Canada (1969)] and independently, J. A. Bondy [Can. Math. Bull. 15, 57–62 (1972; Zbl 0238.05115)] proved that the generalized Petersen graph \(P(n,2)\) is non-Hamiltonian if \(n = 5\pmod 6\), while A. G. Thomason [J. Graph Theory 6, 216–221 (1982; Zbl 0495.05025)] proved that it has precisely 3 Hamiltonian cycles if \(n = 3 \pmod 6\). The Hamiltonian cycles in the remaining generalized Petersen graphs were enumerated by A. J. Schwenk [J. Comb. Theory, Ser. B 47, No. 1, 53–59 (1989; Zbl 0626.05038)]. In this note we give a short unified proof of these results using Grinberg’s theorem.

05C45 Eulerian and Hamiltonian graphs