# A conjecture on the prevalence of cubic bridge graphs

Jerzy A. Filar; Michael Haythorpe; Giang T. Nguyen

Discussiones Mathematicae Graph Theory (2010)

- Volume: 30, Issue: 1, page 175-179
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topJerzy A. Filar, Michael Haythorpe, and Giang T. Nguyen. "A conjecture on the prevalence of cubic bridge graphs." Discussiones Mathematicae Graph Theory 30.1 (2010): 175-179. <http://eudml.org/doc/270864>.

@article{JerzyA2010,

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.},

author = {Jerzy A. Filar, Michael Haythorpe, Giang T. Nguyen},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {Hamiltonian graph; non-Hamiltonian graph; cubic bridge graph},

language = {eng},

number = {1},

pages = {175-179},

title = {A conjecture on the prevalence of cubic bridge graphs},

url = {http://eudml.org/doc/270864},

volume = {30},

year = {2010},

}

TY - JOUR

AU - Jerzy A. Filar

AU - Michael Haythorpe

AU - Giang T. Nguyen

TI - A conjecture on the prevalence of cubic bridge graphs

JO - Discussiones Mathematicae Graph Theory

PY - 2010

VL - 30

IS - 1

SP - 175

EP - 179

AB - 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.

LA - eng

KW - Hamiltonian graph; non-Hamiltonian graph; cubic bridge graph

UR - http://eudml.org/doc/270864

ER -

## References

top- [1] B. Bollobas, Random Graphs (Cambridge University Press, 2001), doi: 10.1017/CBO9780511814068. Zbl0979.05003
- [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. Zbl1118.05062
- [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. Zbl1203.05091
- [4] A.S. Lague, Les reseaux (ou graphes), Memorial des sciences math. 18 (1926).
- [5] B.D. McKay, website for nauty: http://cs.anu.edu.au/ bdm/nauty/.
- [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 Zbl0918.05062
- [7] G.T. Nguyen, Hamiltonian cycle problem, Markov decision processes and graph spectra, PhD Thesis (University of South Australia, 2009).
- [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. Zbl0795.05088

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.