A conjecture on the prevalence of cubic bridge graphs
Jerzy A. Filar ; Michael Haythorpe ; Giang T. Nguyen
Discussiones Mathematicae Graph Theory, Tome 30 (2010), p. 175-179 / Harvested from The Polish Digital Mathematics Library
Access to full text
Full (PDF)

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.

Publié le : 2010-01-01
EUDML-ID : urn:eudml:doc:270864 
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1485,
     author = {Jerzy A. Filar and Michael Haythorpe and Giang T. Nguyen},
     title = {A conjecture on the prevalence of cubic bridge graphs},
     journal = {Discussiones Mathematicae Graph Theory},
     volume = {30},
     year = {2010},
     pages = {175-179},
     zbl = {1214.05070},
     language = {en},
     url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1485}
}

Jerzy A. Filar; Michael Haythorpe; Giang T. Nguyen. A conjecture on the prevalence of cubic bridge graphs. Discussiones Mathematicae Graph Theory, Tome 30 (2010) pp. 175-179. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1485/

[000] [1] B. Bollobas, Random Graphs (Cambridge University Press, 2001), doi: 10.1017/CBO9780511814068. | Zbl 0979.05003

[001] [2] 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. | Zbl 1118.05062

[002] [3] 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. | Zbl 1203.05091

[003] [4] A.S. Lague, Les reseaux (ou graphes), Memorial des sciences math. 18 (1926).

[004] [5] B.D. McKay, website for nauty: http://cs.anu.edu.au/ bdm/nauty/.

[005] [6] 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 | Zbl 0918.05062

[006] [7] G.T. Nguyen, Hamiltonian cycle problem, Markov decision processes and graph spectra, PhD Thesis (University of South Australia, 2009).

[007] [8] R. Robinson and N. Wormald, Almost all regular graphs are Hamiltonian, Random Structures and Algorithms 5 (1994) 363-374, doi: 10.1002/rsa.3240050209. | Zbl 0795.05088