ISSN 1234-3099 (print version)
ISSN 2083-5892 (electronic version)
SCImago Journal Rank (SJR) 2018: 0.763
Rejection Rate (2017-2018): c. 84%
Discussiones Mathematicae Graph Theory 30(1) (2010)
CIAM, University of South Australia
Université Libre de Bruxelles
Keywords: Hamiltonian graph, non-Hamiltonian graph,
cubic bridge graph.
2010 Mathematics Subject Classification: 05C45.
In 1994, Robinson and Wormald  proved a striking result, which
states that almost all d-regular graphs are Hamiltonian, for d
The interested reader is referred to  for an excellent
discussion on Hamiltonian cycles in regular graphs.
All graphs in this note are connected and undirected. A cubic, or
3-regular, graph is a graph where every vertex is connected to exactly
three other vertices. More generally, in a k-regular 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 non-Hamiltonian otherwise. One statement of the famous NP-complete
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 non-Hamiltonian . 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
non-Hamiltonian graphs: bridge graphs, to which we refer as
easy non-Hamiltonian graphs, and non-Hamiltonian graphs that are not
bridge graphs, are hard non-Hamiltonian graphs.
From numerical experiments using GENREG software  and the
cubhamg utility in the package nauty  on cubic graphs of various
orders, we observe that bridge graphs constitute the majority of
non-Hamiltonian graphs. Moreover, as the graph order N increases, so does
the ratio of cubic bridge graphs over all cubic non-Hamiltonian graphs of the
same order. This can be seen from Table 1.
For cubic graphs of order 40 and 50, we consider a 1000000-graph sample for
each order. The observed ratios of cubic bridge graphs to cubic non-Hamiltonian
graphs in Table 2 are even closer to 1. This naturally gives
rise to a conjecture on the prevalence of cubic bridge graphs.
If the above conjecture were, indeed, true it would be possible to argue
that the difficulty of the NP-completeness of the HCP for cubic graphs is
even more of an anomaly than indicated by the result of .
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 non-Hamiltonian and if not, then it is even more likely to be Hamiltonian
than might have been expected on the basis of  alone.
Furthermore, it is reasonable to assume that if the conjecture holds for
cubic graphs then its obvious extension to all d-regular graphs (with
d ≥ 3) will also hold. The underlying intuition is that, somehow, the
"easiest" way to create non-Hamiltonian, d-regular, 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 
may be worth pursuing. Another, approach could, perhaps, be based on the
location of bridge graphs in the 2-dimensional multifilar structure introduced
in  and .
We include an adaptation of Figure 5.1 from , 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
(1-tλi)-1 to be [1/N]∑i (1-tλi)-1, and the
variance function σ2(A,t) to be [1/N]∑i(1-tλi)-2-μ2(A,t). Let t = 1/9 and plot the mean-variance
coordinates (μ(A,t),σ2(A,t)) across all cubic graphs of order 14
in Figure 1. We obtain a self-similar multifilar structure,
zooming into each large and approximately linear cluster reveals smaller,
also approximately linear, clusters with different slopes and between-distances
. Figure 1 indicates that bridge graphs are at, or near,
the top of their clusters.
Figure 1. Mean-variance 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.
Received 8 March 2010
Accepted 8 March 2010