Grinberg's Criterion. (January 2019)

• Record Type: Journal Article
• Authors: Brinkmann, Gunnar; Zamfirescu, Carol T.
• Is Part Of: European journal of combinatorics. Volume 75(2019)
• Page Start: 32
• Page End: 42
• Publication Date: 2019-01
• Subjects: Combinatorial analysis -- Periodicals; Analyse combinatoire -- Périodiques; Combinatorial analysis; Periodicals; Electronic journals; 511.6
• DOI: 10.1016/j.ejc.2018.07.017
• Languages: English
• ISSNs: 0195-6698

Abstract

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.