Haythorpe, Michael


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

Author(s): Haythorpe

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 $?

Keywords: Hamiltonian, Bridge, 3-regular, 1-connected

Syndicate content