Discussiones Mathematicae Graph Theory 30(1) (2010)
175179
doi: 10.7151/dmgt.1485
Jerzy A. Filar, Michael Haythorpe
CIAM, University of South Australia  Giang T. Nguyen
Département d'informatique 
Keywords: Hamiltonian graph, nonHamiltonian graph, cubic bridge graph.
2010 Mathematics Subject Classification: 05C45.
In 1994, Robinson and Wormald [8] proved a striking result, which states that almost all dregular graphs are Hamiltonian, for d ≥ 3. The interested reader is referred to [1] for an excellent discussion on Hamiltonian cycles in regular graphs.
All graphs in this note are connected and undirected. A cubic, or 3regular, graph is a graph where every vertex is connected to exactly three other vertices. More generally, in a kregular graph, every vertex is connected to exactly k other vertices. A Hamiltonian cycle is a simple cycle that goes through every vertex in the graph exactly once. A graph is Hamiltonian if it possesses at least one Hamiltonian cycle, and nonHamiltonian otherwise. One statement of the famous NPcomplete Hamiltonian cycle problem (HCP) is: given a graph, determine whether it is Hamiltonian.
Given a graph, a bridge is an edge the removal of which disconnects the graph. A bridge graph is a graph that contains at least one bridge. Bridge graphs are nonHamiltonian [4]. Moreover, it is straightforward that we can detect bridge graphs in polynomial time. In this note, we consider two exhaustive and mutually exclusive subsets of nonHamiltonian graphs: bridge graphs, to which we refer as easy nonHamiltonian graphs, and nonHamiltonian graphs that are not bridge graphs, are hard nonHamiltonian graphs.
From numerical experiments using GENREG software [6] and the cubhamg utility in the package nauty [5] on cubic graphs of various orders, we observe that bridge graphs constitute the majority of nonHamiltonian graphs. Moreover, as the graph order N increases, so does the ratio of cubic bridge graphs over all cubic nonHamiltonian graphs of the same order. This can be seen from Table 1.
Graph Order  Number of  Number of Cubic  Number of Cubic  Ratio of 

N  Cubic Graphs  NonH Graphs  Bridge Graphs  Bridge/NonH 
10  19  2  1  0.5000 
12  85  5  4  0.8000 
14  509  35  29  0.8286 
16  4060  219  186  0.8493 
18  41301  1666  1435  0.8613 
20  510489  14498  12671  0.8740 
22  7319447  148790  131820  0.8859 
24  117940535  1768732  1590900  0.8995 
For cubic graphs of order 40 and 50, we consider a 1000000graph sample for each order. The observed ratios of cubic bridge graphs to cubic nonHamiltonian graphs in Table 2 are even closer to 1. This naturally gives rise to a conjecture on the prevalence of cubic bridge graphs.
Graph Order  Number of  Number of Cubic  Number of Cubic  Ratio of 
N  Cubic Graphs  NonH Graphs  Bridge Graphs  Bridge/NonH 
40  1000000  912  855  0.9375 
50  1000000  549  530  0.9650 

If the above conjecture were, indeed, true it would be possible to argue that the difficulty of the NPcompleteness of the HCP for cubic graphs is even more of an anomaly than indicated by the result of [8]. In particular, if an arbitrary cubic graph is considered, a polynomial algorithm can tell us whether or not it is a bridge graph. If it is, then it is nonHamiltonian and if not, then it is even more likely to be Hamiltonian than might have been expected on the basis of [8] alone.
Furthermore, it is reasonable to assume that if the conjecture holds for cubic graphs then its obvious extension to all dregular graphs (with d ≥ 3) will also hold. The underlying intuition is that, somehow, the "easiest" way to create nonHamiltonian, dregular, graphs with N vertices is to join via bridges graphs with fewer than N vertices. Regrettably, we do not know how to prove the stated conjecture. An approach, based on recursive counting arguments, along those outlined in Chapter 5 of Nguyen [7] may be worth pursuing. Another, approach could, perhaps, be based on the location of bridge graphs in the 2dimensional multifilar structure introduced in [2] and [3].
We include an adaptation of Figure 5.1 from [3], but here we only distinguish bridge graphs, represented by crosses, from the rest. Given a graph of order N, let λ_{i} be eigenvalues of the adjacency matrix A. Define the expected value function μ(A,t) of (1tλ_{i})^{1} to be [1/N]∑_{i} (1tλ_{i})^{1}, and the variance function σ^{2}(A,t) to be [1/N]∑_{i}(1tλ_{i})^{2}μ^{2}(A,t). Let t = 1/9 and plot the meanvariance coordinates (μ(A,t),σ^{2}(A,t)) across all cubic graphs of order 14 in Figure 1. We obtain a selfsimilar multifilar structure, zooming into each large and approximately linear cluster reveals smaller, also approximately linear, clusters with different slopes and betweendistances [3]. Figure 1 indicates that bridge graphs are at, or near, the top of their clusters.
Figure 1. Meanvariance plot for all cubic graphs of order 14.
The authors gratefully acknowledge helpful discussions with V. Ejov and B.D. McKay and the support under Australian Research Council (ARC) Discovery Grants No. DP0666632 and DP0984470.
[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) 236246, 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) 13671379, 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) 137146, doi: 10.1002/(SICI)10970118(199902)30:2<137::AIDJGT7>3.0.CO;2G. 
[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) 363374, doi: 10.1002/rsa.3240050209. 
Received 8 March 2010
Accepted 8 March 2010