Home » Subject » Graph Theory » Basic G.T.

Almost all non-Hamiltonian 3-regular graphs are 1-connected

Importance: Medium ✭✭
Author(s): Haythorpe, Michael
Subject: Graph Theory
» Basic Graph Theory
Keywords: Hamiltonian, Bridge, 3-regular, 1-connected
Recomm. for undergrads: yes
Posted by: mhaythorpe
on: August 23rd, 2013
Conjecture   Denote by $ NH(n) $ the number of non-Hamiltonian 3-regular graphs of size $ 2n $, and similarly denote by $ NHB(n) $ the number of non-Hamiltonian 3-regular 1-connected graphs of size $ 2n $.

Is it true that $ \lim\limits_{n \rightarrow \infty} \displaystyle\frac{NHB(n)}{NH(n)} = 1 $?

A stronger version of this conjecture asks whether it is also the case that $ \displaystyle\frac{NHB(n)}{NH(n)} > \displaystyle\frac{NHB(k)}{NH(k)} $ for all $ n > k $.

Experimental data was given by Filar et al [FHN] demonstrating that the strong conjecture is satisfied for all $ n \leq 12 $, and with sampled data provided for $ n = 20 $ and $ n = 25 $. No further results have been forthcoming.

The experimental data can be viewed at http://dx.doi.org/10.7151/dmgt.1485

Packers And Movers Chandigarh
Packers And Movers Hyderabad
Packers And Movers Bangalore

Bibliography

[FHN] Jerzy A Filar, Giang T Nguyen, Michael Haythorpe, "A conjecture on the prevalence of cubic bridge graphs", Discussiones Mathematicae Graph Theory 30(1):175--179 (2010).


* indicates original appearance(s) of problem.
add new comment