4
$\begingroup$

Consider the following naive algorithm for finding Hamiltonian cycles on a simple undirected graph G with n vertices:

  1. Choose an arbitrary vertex and mark it as vertex 1
  2. Choose an arbitrary unmarked neighbor of vertex 1, move to it, and mark it as vertex 2
  3. Repeat step (2) while the current iteration i < n and vertex i has unmarked neighbors
  4. If vertex n is adjacent to vertex 1, move to vertex 1 and terminate

It seems pretty intuitive to me that this algorithm fails to find Hamiltonian cycles most of the time on most graphs. However, there are some graphs for which this algorithm will always produce a Hamiltonian cycle, no matter where it starts or which subsequent vertices it chooses. As far as I'm aware, these graphs are: (1) a cycle on n vertices, (2) a complete bipartite graph on n vertices where the partite sets have the same magnitude, and (3) the complete graph on n vertices. I could be overlooking something, but I think it's trivial to show this. But for every graph other than these three types of graphs, I'm pretty sure there is at least one instance where the algorithm fails. The thing is I'm having a lot of trouble explicitly showing this.

I tried breaking the cases up into non-regular and regular graphs (not including the 3 mentioned above), but I'm struggling to show the non-regular case, let alone the regular case. My general approach is to consider a graph G that has at least one Hamiltonian cycle, but isn't one of those three graphs and then somehow manipulate that cycle to construct a "failed attempt" for the algorithm. Needless to say, it isn't working out. I think there might be some form of combinatorial argument, but I don't really know how to start going about finding it, since G can be almost any simple undirected graph. All of the theorems I looked at aren't of much help because they are about the existence of a hamiltonian cycle, but I'm looking for (vaguely) for the lack of one. So at this point, I'm stuck.

So to summarize my question: how can one explicitly show that for any graph that isn't one of the three graphs listed above, the algorithm has a non zero probability of failure?

$\endgroup$
  • $\begingroup$ Nice problem. My first thought is that if there is any edge that doesn't belong to a Hamilton cycle, the algorithm may fail, since that might be the first edge we choose. Are there graphs besides your examples where each edge belongs to a Hamilton cycle? Yes, for example a regular octagon with a diagonal joining each pair of diametrically opposite vertices. Can the algorithm fail in this case? I'm not sure. $\endgroup$ – saulspatz Apr 24 at 6:34
  • 2
    $\begingroup$ The paper @bof linked to does indeed prove that the three types of graph ($C_n$, $K_n$, $K_{2m,2m}$) are the only ones that are randomly Hamiltonian. $\endgroup$ – Jaap Scherphuis Apr 24 at 8:21
3
$\begingroup$

The paper "Randomly Traceable Graphs" by Gary Chartrand and Hudson V. Kronk tackles this question, and confirms that the three types of graph ($C_n$, $K_n$, $K_{m,m}$) are the only ones:
https://epubs.siam.org/doi/abs/10.1137/0116056

Randomly Traceble graphs are graphs where every random self-avoiding path eventually visits all vertices (i.e. becomes a Hamiltonian path).

Randomly Hamiltonian graphs are Randomly Traceble graphs where every one of those random Hamiltonian paths can be closed to become a Hamiltonian cycle.

The paper first proves that all Randomly Traceble graphs with $n\ge3$ are randomly Hamiltonian. This is simple: Given any randomly traceable graph with a Hamiltonian path $v_1$, $v_2$, ..., $v_n$. The path $v_2$, ..., $v_n$, must be extendable to a Hamiltonian path since the graph is Randomly Traceable. Therefore $v_n$ and $v_1$ are connected by an edge, and any Hamiltonian path can be closed to become a Hamiltonian cycle. In the rest of the paper this trick of proving an edge must be present by constructing a hamiltonian path between its two vertices is repeatedly used.

The paper then views any Randomly Traceable graph as an outer (Hamiltonian) n-cycle possibly with diagonals.
If it has no diagonals, then it is just a cycle graph $C_n$.
If it has triangles (formed by two outer edges and one diagonal) then it turns out that all diagonals must be present and it is a complete graph $K_n$.
If instead it has 4-cycles (formed by three outer edges and one diagonal) then it turns out that it must be $K_{n/2,n/2}$ with $n$ even.
If it has larger cycles, then it will also have triangles, so no other types of randomly Hamiltonian graphs exist.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ A proof of the characterization is also given in Behzad & Chartrand, Introduction to the Theory of Graphs, Theorem 11.5. $\endgroup$ – bof Apr 24 at 9:21

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.