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

Abstract

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

How to cite

top

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

top

You must be logged in to post comments.