Discussiones Mathematicae Graph Theory 30(1) (2010) 175-179
doi: 10.7151/dmgt.1485

[BIBTex] [PDF] [PS]

A CONJECTURE ON THE PREVALENCE OF CUBIC BRIDGE GRAPHS

Jerzy A. Filar,  Michael Haythorpe

CIAM, University of South Australia

Giang T. Nguyen

Département d'informatique
Université Libre de Bruxelles

Abstract

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.

Keywords: Hamiltonian graph, non-Hamiltonian graph, cubic bridge graph.

2010 Mathematics Subject Classification: 05C45.

1. A Conjecture

In 1994, Robinson and Wormald [8] proved a striking result, which states that almost all d-regular 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 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 [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 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 [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 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.

Table 1. Ratio of cubic bridge graphs over cubic non-Hamiltonian graphs, of order 10 to 22.

Graph Order Number of Number of Cubic Number of Cubic Ratio of
N Cubic Graphs Non-H Graphs Bridge Graphs Bridge/Non-H
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 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.

Table 2. Ratio of cubic bridge graphs over cubic non-Hamiltonian graphs, of order 40 and 50.

Graph Order Number of Number of Cubic Number of Cubic Ratio of
N Cubic Graphs Non-H Graphs Bridge Graphs Bridge/Non-H
40 1000000 912 855 0.9375
50 1000000 549 530 0.9650
Conjecture 1. Consider cubic graphs of order N.

lim
N → ∞ 
#cubic bridge graphs
#cubic non-Hamiltonian graphs
=

lim
N → ∞ 
#cubic easynon-Hamiltonian graphs
#[cubic easy non-Hamiltonian graphs +cubic hard non-Hamiltonian graphs]
= 1.

2. Discussion

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 [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 non-Hamiltonian 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 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 [7] may be worth pursuing. Another, approach could, perhaps, be based on the location of bridge graphs in the 2-dimensional 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 (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)-22(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 [3]. 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.

Acknowledgements

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.

References

[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.

Received 8 March 2010
Accepted 8 March 2010