Suppose we have a graph $G$, which for sake of convenience we'll require to be vertex-transitive. Then there's a natural notion of a random path: start at any vertex $v_1$ (and this is where the vertex-transitivity is used), and from a vertex $v_i$ choose $v_{i+1}$ with equal probability from all the neighbors of $v_i$ that haven't been visited yet. If $v_i$ has no unchosen neighbors, the path terminates. If $G$ has any Hamiltonian paths, then clearly there is a non-zero probability that a path chosen this way will be Hamiltonian; the question is, what is the probability that it is?
There are a couple of trivial cases: if we have a cycle graph $C_n$ or a complete graph $K_n$ then the probability is clearly $1$. (For $C_n$ once we've made our first choice we have no other choices to make, and for $K_n$ as long as there are unused vertices there's a path from that vertex.) But already for a graph as simple as $D_{2n}$ (two copies of $C_n$ with edges between corresponding nodes) it's not clear to me what the probability is, or even what the asymptotics are.
Has this probability been studied, either for specific graphs $G$ (the Petersen graph immediately springs to mind) or for families of graphs like $D_{2n}$ or $\mathbb{Z}_2^n$? Is there any known characterization of the graphs where a Hamiltonian path will always be found this way? Does anyone have references to similar problems? Many thanks in advance!
Chartrand and Kronk called these "randomly traceable graphs" in the paper with the same title (https://doi.org/10.1137/0116056). They completely characterize the possibilities. Aside from $C_n$ and $K_n$, there is only one more case: when $n$ is even, the complete bipartite graph $K_{n/2,n/2}$ is randomly traceable.