On Grinberg’s Criterion
Date
2019
Authors
Brinkmann, Gunnar
Zamfirescu, Carol T.
Journal Title
Journal ISSN
Volume Title
Publisher
Universiteit Gent, Faculty of Science
Abstract
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 Gehner and Shimamoto), 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 Bondy and Häggkvist.
See full version of the article: https://www.sciencedirect.com/science/article/pii/S0195669818301343
Description
Keywords
Grinberg’s Criterion, Hamiltonian cycle, 2-factor, spanning walks