PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2010 | 30 | 1 | 175-179
Tytuł artykułu

A conjecture on the prevalence of cubic bridge graphs

Treść / Zawartość
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
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.
Wydawca
Rocznik
Tom
30
Numer
1
Strony
175-179
Opis fizyczny
Daty
wydano
2010
otrzymano
2010-03-08
zaakceptowano
2010-03-08
Twórcy
  • CIAM, University of South Australia
  • CIAM, University of South Australia
  • Département d'informatique, Université Libre de Bruxelles
Bibliografia
  • [1] B. Bollobas, Random Graphs (Cambridge University Press, 2001), doi: 10.1017/CBO9780511814068.
  • [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.
  • [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.
  • [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
  • [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.
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1485
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.