Grinberg's Criterion Applied to Some Non-Planar Graphs

G. L. Chia, Carsten Thomassen

    Research output: Contribution to journalJournal articleResearchpeer-review

    443 Downloads (Pure)

    Abstract

    Robertson ([5]) and independently, Bondy ([1]) proved that the generalized Petersen graph P(n, 2) is non-hamiltonian if n equivalent to 5 ( mod 6), while Thomason [7] proved that it has precisely 3 hamiltonian cycles if n equivalent to 3 (mod 6). The hamiltonian cycles in the remaining generalized Petersen graphs were enumerated by Schwenk [6]. In this note we give a short unified proof of these results using Grinberg's theorem.
    Original languageEnglish
    JournalArs Combinatoria
    Volume100
    Pages (from-to)3-7
    ISSN0381-7032
    Publication statusPublished - 2011

    Fingerprint

    Dive into the research topics of 'Grinberg's Criterion Applied to Some Non-Planar Graphs'. Together they form a unique fingerprint.

    Cite this