On the number of cycles in planar graphs

K. Buchin, C. Knauer, K. Kriegel, A. Schulz, R. Seidel

    Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

    37 Citations (Scopus)
    266 Downloads (Pure)

    Abstract

    We investigate the maximum number of simple cycles and the maximum number of Hamiltonian cycles in a planar graph G with n vertices. Using the transfer matrix method we construct a family of graphs which have at least 2.4262 n simple cycles and at least 2.0845 n Hamilton cycles. Based on counting arguments for perfect matchings we prove that 2.3404 n is an upper bound for the number of Hamiltonian cycles. Moreover, we obtain upper bounds for the number of simple cycles of a given length with a face coloring technique. Combining both, we show that there is no planar graph with more than 2.8927 n simple cycles. This reduces the previous gap between the upper and lower bound for the exponential growth from 1.03 to 0.46.
    Original languageEnglish
    Title of host publicationComputing and Combinatorics (13th Annual International Conference, COCOON 2007, Banff, Canada, July 16-19, 2007. Proceedings)
    EditorsG. Lin
    Place of PublicationBerlin
    PublisherSpringer
    Pages97-107
    ISBN (Print)978-3-540-73544-1
    DOIs
    Publication statusPublished - 2007

    Publication series

    NameLecture Notes in Computer Science
    Volume4598
    ISSN (Print)0302-9743

    Fingerprint

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

    Cite this