Determining whether Hamiltonian cycles exist in graphs is an NP-complete problem, so it is no wonder that the Combinatorica function HamiltonianCycle is slow for large graphs. Theorems by Dirac, Ore, Pósa, and Chvátal provide sufficient conditions that are easy to check for the existence of such cycles. This article provides Mathematica programs for those conditions, thus extending the capability of HamiltonianQ, which only tests the biconnectivity—a simple necessary condition—of a given graph. We also investigate experimentally the limiting behavior of whether the conditions are fulfilled for large random graphs. The phenomenon seen is proved as a theorem, closely related to earlier results by Karp and Pósa.

Introduction

The Combinatorica function HamiltonianCycle seems to work slowly for large graphs, because finding a Hamiltonian cycle in graphs is obviously an NP-complete problem. The search can be made faster, starting by testing if such a cycle exists at all. The Combinatorica function HamiltonianQ does this by checking the biconnectivity of the graph, which is a simple necessary condition for the existence of a Hamiltonian cycle. However, further conditions are easy to check, formulated in theorems by Dirac [1], Ore [2], Pósa [3], and Chvátal [4]. (See also [5, 6, 7].) It saves time to apply these criteria before trying to construct a Hamiltonian cycle. We think that the present algorithms might also help improve other functions in the Combinatorica Package, such as TravelingSalesman.

All of our algorithms are deterministic; however, probabilistic algorithms are also known for the same problem, see Angluin and Valiant [8].

The structure of our paper is as follows. First we define the functions that test the conditions in the theorems by Dirac, Ore, Pósa, and Chvátal and we apply these functions to all the graphs in FiniteGraphs. Two examples are shown to prove that the conditions are different. Next, a few examples are used to show that in some cases the HamiltonianCycle function takes more time than one of our functions using the simplest necessary condition. Experiments on large Erdős-Rényi random graphs as (the number of vertices) tends to infinity follow, leading to a conjecture that if ( is the probability of an edge), then the conditions are typically fulfilled, and if , then they are typically violated. This is in accordance with the results of Pósa [9] and Karp (see [4]). The conjecture is finally rigorously proved and also illustrated.

Functions

We need these two packages.

First of all, the function RequireQ verifies the necessary condition that all of the vertices of the graph should have at least two neighbors.

Next we test four sufficient conditions formulated as in [10].

Dirac’s theorem

A simple graph with graph vertices in which each vertex has degree at least has a Hamiltonian cycle.

Ore’s theorem

If a simple graph G has graph vertices and every pair of vertices that are not joined by an edge has a sum of degrees that is greater than , then G has a Hamiltonian cycle.

Pósa’s theorem

If a simple graph G has degrees where and if , then G has a Hamiltonian cycle.

Chvátal’s theorem

If a simple graph G has degrees where and, when , then holds, then G has a Hamiltonian cycle.

Examples

In these examples we can see the usefulness of the theorems.

These functions run fast, but would take 10 hours. That shows that the Hamiltonian cycles are found times more slowly than the theorems compute which graphs surely have a Hamiltonian cycle. If one has many large graphs but needs only a single Hamiltonian cycle in any one of them, these functions should be run first.

In the following individual examples, HamiltonianCycle runs 10 times more slowly than the theorems. The difference grows with the size of the graphs because searching for Hamiltonian cycles is an complexity problem and the complexity of the theorems is only .

These two examples also illustrate that the theorems do not always give the same result. However it is easy to see the connection between Dirac’s theorem and Ore’s theorem, because satisfying the conditions of Dirac’s theorem implies that the conditions of Ore’s theorem are also satisfied. There are more implications between these theorems, which are not as easy to prove: the conditions of Ore’s theorem imply those of Pósa’s theorem and the conditions of Pósa’s theorem imply those of Chvátal’s theorem.

A graph is biconnected if for every two vertices and of , there are two disjoint simple paths between and . The built-in function HamiltonianQ only tests the biconnectivity of the graph, and if the graph is biconnected, it runs the HamiltonianCycle function. So if the graph is biconnected then it is slower than the theorems. The RequireQ function may provide a negative result more quickly.

An even more convincing example of the same type follows.

Here is an example for the difference in a large graph.

Here we can see that in huge graphs it is better to run the RequireQ function first, because it is possible that Mathematica will search for a long time when there is no Hamiltonian cycle in the graph at all. So it might be useful to build the function RequireQ into the HamiltonianQ and HamiltonianCycle functions in Mathematica.

Limit Values in Large Graphs

In applying the theorems for large Erdős-Rényi random graphs (see [11]) using Mathematica, a question emerges: what kinds of limit do exist?

Let denote the probability of the existence of an edge. We wonder what happens if is fixed and the number of vertices tends to infinity.

As can be seen in the previous example, Pósa’s theorem or Chvátal’s theorem is more efficient than the others because they gave True and the others did not, so let us use only these two.

Our simulation results have shown that in a random graph with a hundred vertices with probability 0.48 for an edge, the conditions of the theorems are violated in about 99.6% of the cases. However, changing the edge probability to 0.52 implies that the conditions of the theorems are satisfied in about 98.8% of the cases.

Let us try these limits in graphs with a thousand vertices.

The ratios seem to be the same, but it is very difficult to compute the relevant probabilities. Here is a table with the test results.

Theorem

Let be the probability of an edge and be any positive number. If and , then the probability of satisfying the conditions of the four theorems tends to 1, and if and , then the probability of satisfying the conditions of the four theorems tends to 0.

Proof

Number the vertices with a bijective function .

When , change the edges of the graph with these rules:

If :

Delete the edge if .

Direct the edge if .

Direct the edge if .

We can examine the distribution of in-degrees and out-degrees separately.

With this construction the sum of the in-degree and out-degree for each vertex is less than or equal to the degree of in the original graph.

The distribution of in-degrees of is for even or for odd . Let us work with the worst case.

, where for all . By the central limit theorem (CLT), .

It is well known that for all if .

The speed of convergence of the CLT is at least on the order of .

Let .

Then

If , then for large , so .

(This is because .)

So the probability that all in-degrees are greater than tends to 1. We can prove the same for the out-degrees, so all of the degrees will be greater than in the original graph. Then the probability of satisfying the conditions of Dirac’s theorem tends to 1 and the same holds for the other three theorems.

When , direct the edges of the graph using the following rules if .

Double the edge and direct them in opposite ways, and , if .

Direct the edge if .

Direct the edge if .

With this construction the sum of the in-degree and out-degree for each vertex is greater than or equal to the degree of in the original graph.

The distribution of the in-degree of is if is odd or if is even. Let us work with the worst case.

Let and .

Then
.

If , then for large , so
.

So the probability that all the in-degrees are less than tends to 1. We can prove the same for the out-degrees, so all degrees will be less than in the original graph.

Then the probability of satisfying the conditions of Chvátal’s theorem tends to 0, and the same holds for the other three theorems.

Some illustrations of the proof follow.

Here we can see that the distribution of the degrees is near to , where is the number of the vertices and denotes the probability of the existence of an edge.

Let ; if we fix (or ) and the number of vertices tends to infinity, then .

Our results are related to some earlier results.

R. M. Karp (see [4]): is Hamiltonian with probability if .

L. Pósa [9]: Almost all graphs with vertices and edges are Hamiltonian.

With these theorems it is easy to see that if and , then the probability that is Hamiltonian tends to 1. Moreover these theorems imply that if is independent of and , then the probability that is Hamiltonian tends to 1.

The experiments show that the theorems are not only useful, but also raise interesting questions.

Acknowledgments

I wish to thank Gábor Wiener and Gábor Borbély for stimulating discussions and suggestions. The help of Ágnes Tóth both in programming and theory is highly appreciated. I am grateful to Daniel Lichtblau and Ambrus Zsbán, who gave ideas for the proof.

References

About the Authors

Csongor Gy. Csehi is pursuing his B.Sc. in mathematics at the Budapest University of Technology and Economics. His main research interest is Hamiltonian cycles and semirandom graphs, and also the graphicity of the sum of graphic matroids. He has another accepted paper beyond the present one, with coauthors, entitled “On the Rectifiability Condition of a Second-Order Differential Equation in Special Finsler Spaces.”

János Tóth received his M.Sc. in mathematics at the Loránd Eötvös University of Budapest in 1971 and his Ph.D. from the Hungarian Academy of Sciences in 1986. Currently he is associate professor at the Department of Analysis of the Technical University of Budapest, Hungary, and participates in teaching at Loránd Eötvös University as well. He is the author of Mathematical Models of Chemical Reactions (with P. Érdi), Mathematics and Mathematica (with L. Szili, in Hungarian), Research and Publication in Science (with P. Csermely, T. Koltay, and P. Gergely, in Hungarian), and Differential Equations. An Introduction to the Theory with Applications (with P. L. Simon, in Hungarian).

Csongor Gy. Csehi
Mathematical Institute of Budapest University of Technology and Economics
Egry J. u. 1., H ép.
H-1111 Budapest, Hungary
cscsgy@math.bme.hu

János Tóth
Mathematical Institute of Budapest University of Technology and Economics
Egry J. u. 1., H ép.
H-1111 Budapest, Hungary
jtoth@math.bme.hu