5
$\begingroup$

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$.

Improve this question
$\endgroup$
9
  • $\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
    Commented Feb 3, 2017 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
    Commented Feb 3, 2017 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
    Commented Feb 3, 2017 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
    Commented Feb 3, 2017 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
    Commented Feb 3, 2017 at 14:13

0

Reset to default

You must log in to answer this question.