6533b7d6fe1ef96bd1266a5b
RESEARCH PRODUCT
On Grinberg’s Criterion
Gunnar BrinkmannCarol T. Zamfirescusubject
Grinberg’s Criterion Hamiltonian cycle 2-factor spanning walksdescription
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
| year | journal | country | edition | language |
|---|---|---|---|---|
| 2019-01-01 |