On the number of cycles in planar graphs

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

    Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

    37 Citaten (Scopus)
    139 Downloads (Pure)


    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.
    Originele taal-2Engels
    TitelComputing and Combinatorics (13th Annual International Conference, COCOON 2007, Banff, Canada, July 16-19, 2007. Proceedings)
    RedacteurenG. Lin
    Plaats van productieBerlin
    ISBN van geprinte versie978-3-540-73544-1
    StatusGepubliceerd - 2007

    Publicatie series

    NaamLecture Notes in Computer Science
    ISSN van geprinte versie0302-9743

    Vingerafdruk Duik in de onderzoeksthema's van 'On the number of cycles in planar graphs'. Samen vormen ze een unieke vingerafdruk.

    Citeer dit