A conjecture on the prevalence of cubic bridge graphs
A conjecture on the prevalence of cubic bridge graphs
Date
2010
Authors
Filar, Jerzy A
Haythorpe, Michael
Nguyen, Giang T
Journal Title
Journal ISSN
Volume Title
Publisher
Technical University Press, University of Zielona Gora
Abstract
Almost all d-regular graphs are Hamiltonian, for d ≥ 3. 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.
Description
Keywords
Mathematics,
Hamiltonian cycle problem,
Graph theory
Citation
Filar, J.A., Haythorpe, M. and Nguyen, G.T., 2010. A conjecture on the prevalence of cubic bridge graphs. Discussiones Mathematicae Graph Theory, 30(1), 175-179.