A graph is uniquely hamiltonian if it has exactly one hamiltonian cycle.

According to a conjecture there are no $r$-regular uniquely hamiltonian graphs for $r > 2$ and of special interest is the case $r=4$ ($r=3$ is solved).

The following graph gadget (if it exists) will give $4$-regular uniquely hamiltonian graph:

$G$ is finite simple connected graph. Two vertices $u,v$ are of degree $3$ and the rest vertices are of degree $4$. There is exactly one $u-v$ hamiltonian path.

Does such gadget exist?

Computer search didn't find any on up to 12 vertices.

The $4$-regular graph is two copies of $G$: $G_1$ and $G_2$ and additional edges $u_1 u_2$ and $v_1 v_2$.

  • $\begingroup$ So the conjecture is that a 4-regular uniquely hamiltonian graph doesn't exist, and you are looking for a relatively easy construction which might hopefully yield a counterexample to that. Good luck...! BTW, finding a certain graph with exactly one u−v hamiltonian path should not be that much easier. $\endgroup$ – Wolfgang Feb 3 '17 at 11:40
  • $\begingroup$ @Wolfgang No, I am not trying to do this. Nonexistence won't say anything about the conjecture. I believe such gadget doesn't exist. $\endgroup$ – joro Feb 3 '17 at 11:46
  • $\begingroup$ OK I see. So your goal is rather to rule out a certain category of possible counterexamples, by showing that such a gadget doesn't exist. $\endgroup$ – Wolfgang Feb 3 '17 at 11:50
  • $\begingroup$ Thomason's result says that there are always an even number of Hamiltonian paths in the similar scenario for r=3. Do you have any similar conjecture here, like the number of such paths is always divisible by 3? $\endgroup$ – domotorp Feb 3 '17 at 12:33
  • 1
    $\begingroup$ @domotorp There is no such conjecture about hamilton cycles through an edge in a 4-regular graph, as hamiltonian 4-regular graphs appear to have plenty of hamilton cycles, not just "a second", and the data for small graphs shows that pretty much anything can happen. In fact, if an edge lies in one hamilton cycle, then it seems to lie in at least six (and this only happens for $K_5$) $\endgroup$ – Gordon Royle Feb 3 '17 at 14:13

Your Answer

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

Browse other questions tagged or ask your own question.