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.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.