On the maximum number of cycles in a planar graph

R.E.L. Aldred, Carsten Thomassen

    Research output: Contribution to journalJournal articleResearchpeer-review

    Abstract

    Let G be a graph on p vertices with q edges and let r = q - p + 1. We show that G has at most 15/162(r) cycles. We also show that if G is planar, then G has at most 2(r-1) + o(2(r-1)) cycles. The planar result is best possible in the sense that any prism, that is, the Cartesian product of a cycle and a path with one edge, has more than 2(r-1) cycles.
    Original languageEnglish
    JournalJournal of Graph Theory
    Volume57
    Issue number3
    Pages (from-to)255-264
    ISSN0364-9024
    DOIs
    Publication statusPublished - 2008

    Keywords

    • maximum number of cycles
    • graphs

    Fingerprint Dive into the research topics of 'On the maximum number of cycles in a planar graph'. Together they form a unique fingerprint.

    Cite this