5
$\begingroup$

In short, I would like to know either/both the probability that there exists a Hamiltonian circuit within a graph, or the number of circuits expected to exist. (Without actually finding all the circuits). If I run an algorithm to find all circuits, how many should I expect to find, if any? I am fine with a close approximation if it simplifies the calculations substantially.

If I have a given number of vertices and the average number of edges, is this enough information? Each vertex may have many out-edges but no two vertices share more than one edge. Also, a vertex cannot belong to two circuits. Once a circuit is found, those vertices that comprise it are removed from the graph.

My example graph has 10,000 vertices and each vertex has three out-edges to other vertices.

And a follow up question: How could I formulate the question to figure out the minimum average number of out-edges per vertex to give me an arbitrary level of certainty that I would find at least one circuit? Stated another way, if I want 50% certainty in finding a circuit, and I have 10,000 vertices, what is the minimum number of out-edges each vertex should have? (not the average, but actual minimum)

I have some scratchpad notes where I've worked this out, but would really appreciate the guidance of someone more knowledgeable. Thanks!

$\endgroup$
1
$\begingroup$

The answer depends a lot on how one defines "random cubic graph" with $n$ vertices (necessarily $n$ is even), we may try the following to find Hamilton circuits:

Fix a vertex $a_1$, pick one of its neighbours $a_2$ at random. Then, assuming we have $a_1a_2\ldots a_k$ with $k\ge 2$, toss a coin to decide which of the other two (i.e. $\ne a_{k-1}$) neighbours of $a_k$ to pick as $a_{k+1}$ and continue. It may be adequate to assume that $a_ka_{k+1}$ could be any of the $3(n-k)$ edges to a "new" vertex, or any of the $k-3$ not yet used edges to one of the vertices $a_2,\ldots, a_{k-2}$, or any of the two not yest used edges to $a_1$. This makes us guess that the probability to hit a new vertex is $\frac{3(n-k)}{3(n-k)+(k-3)+2}=1-\frac{k-1}{3n-2k-1} $. And when $k=n$, the probability of succesfully coming back to $a_1$ is $\frac{2}{n-1} $. This would suggest that there are about $$\tag13\cdot 2^n\cdot\prod_{k=2}^{n-1}\frac{3(n-k)}{3n-2k-1}\cdot \frac2{n-1}=3^{n-1}2^{n+1}(n-2)!\frac{(3n/2-3)!\cdot 2^{3n/2-3}}{(3n-5)!\cdot (n/2)!\cdot2^{n/2}}\cdot\frac1{n-1} $$ Hamilton cycles.

Or: There are $\frac12(n-1)!$ Hamilton cycles in the complete graph $K_n$. For each of these, the probability that the first edge is also in $G$, is $\frac3{n-1}$; for later edges, the probybility that the edge is in $G$, given that the previous edge is in $G$, is $\frac{2}{n-2}$; we should make a special consideration for the final edge, but ignore that. With this Hamilton cycle of $K_n$ is also in $G$ with probability $ \frac3{n-1}\cdot\left(\frac2{n-2}\right)^{n-1}$, giving a total expected number of $$ \frac12(n-1)!\cdot \frac3{n-1}\cdot\left(\frac2{n-2}\right)^{n-1}=\frac{3\cdot 2^{n-2}\cdot (n-2)!}{(n-2)^{n-1}}$$ Hamilton cycles. With Stirling, this simplifies to $$\tag2\approx {3\cdot \left(\frac 2e\right)^{n-2}\sqrt{\frac{2\pi}{n-2}}}\approx 0.$$

Or: If we remove a random edge from a cubic graph, we produce two vertices of degree $2$, which can be replaced with an edge directly connectng their neighbours, thus resulting in a cubic graph with two vertices less. However, this step may have produced a double edge, in which case we can drop one of the edges, obtain degree-two vertices again, which can be removed. This could repeat, but for large $n$ we can consider each of these special cases rare. Thus the Hamilton circuits of $G$ that do not use a specific edge are in correspondance with the Hamilton circuits of a smaller cubic graph. For a fixed vertex $a_0$, each Hailton circuit avoids precisely one of the three incident edges. Hence this suggests that the expected number of circuits for an $n$-vertex cubic graph are essentially $3$ times the expected number of the number of circuits in an $(n-2)$-vertex cubic graph, so their count should be $$\tag3 \sim 3^{n/2}.$$

Now that I have heuristically(!) obtained three totally different results, it appears that this answer should rather be considered an oversized comment - sigh.

$\endgroup$
  • $\begingroup$ Thanks Hagen, Your first line of thinking is how I was approaching it too, and I think will work for me. Would the result hold if three were not the actual number of edges of each vertex, but rather the mean number of out-edges per vertex? Also, could you refactor formula(1) to take a variable 'E' instead of a constant as the number of out-edges? $\endgroup$ – Sully Apr 20 '14 at 23:48
  • $\begingroup$ I realized I was asking the 'wrong question,' but you answered what I asked so I'll go ahead and award the answer and thank you for the discussion! $\endgroup$ – Sully Apr 22 '14 at 15:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.