ArticleOriginal scientific text
Title
A conjecture on the prevalence of cubic bridge graphs
Authors 1, 1, 2
Affiliations
- CIAM, University of South Australia
- Département d'informatique, Université Libre de Bruxelles
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.
Keywords
Hamiltonian graph, non-Hamiltonian graph, cubic bridge graph
Bibliography
- B. Bollobas, Random Graphs (Cambridge University Press, 2001), doi: 10.1017/CBO9780511814068.
- V. Ejov, J.A. Filar S.K. Lucas and P. Zograf, Clustering of spectra and fractals of regular graphs, J. Math. Anal. and Appl. 333 (2007) 236-246, doi: 10.1016/j.jmaa.2006.09.072.
- V. Ejov, S. Friedland and G.T. Nguyen, A note on the graph's resolvent and the multifilar structure, Linear Algebra and Its Application 431 (2009) 1367-1379, doi: 10.1016/j.laa.2009.05.019.
- A.S. Lague, Les reseaux (ou graphes), Memorial des sciences math. 18 (1926).
- B.D. McKay, website for nauty: http://cs.anu.edu.au/ bdm/nauty/.
- M. Meringer, Fast generation of regular graphs and construction of cages, J. Graph Ttheory 30 (1999) 137-146, doi: 10.1002/(SICI)1097-0118(199902)30:2<137::AID-JGT7>3.0.CO;2-G
- G.T. Nguyen, Hamiltonian cycle problem, Markov decision processes and graph spectra, PhD Thesis (University of South Australia, 2009).
- R. Robinson and N. Wormald, Almost all regular graphs are Hamiltonian, Random Structures and Algorithms 5 (1994) 363-374, doi: 10.1002/rsa.3240050209.
Pages:
175-179
Main language of publication
English
Received
2010-03-08
Accepted
2010-03-08
Published
2010
DOI: 10.7151/dmgt.1485
Exact and natural sciences