A conjecture on the prevalence of cubic bridge graphs

Jerzy Filar, Michael Haythorpe, Giang Nguyen

    Research output: Contribution to journalArticle

    4 Citations (Scopus)

    Abstract

    Almost all d-regular graphs are Hamiltonian, for d ≥ 3 [8]. In this note we conjecture that in a similar, yet somewhat different, sense almost all cubic non-Hamiltonian graphs are bridge graphs, and present supporting empirical results for this prevalence of the latter among all connected cubic non-Hamiltonian graphs.

    Original languageEnglish
    Pages (from-to)175-179
    Number of pages5
    JournalDiscussiones Mathematicae. Graph Theory
    Volume30
    Issue number1
    DOIs
    Publication statusPublished - 2010

    Keywords

    • Cubic bridge graph
    • Hamiltonian graph
    • Non-Hamiltonian graph

    Fingerprint Dive into the research topics of 'A conjecture on the prevalence of cubic bridge graphs'. Together they form a unique fingerprint.

  • Cite this