A conjecture on the prevalence of cubic bridge graphs

Jerzy Filar, Michael Haythorpe, Giang Nguyen

    Research output: Contribution to journalArticlepeer-review

    4 Citations (Scopus)


    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
    Issue number1
    Publication statusPublished - 2010


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


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

    Cite this