1
$\begingroup$

Related to uniquely hamiltionian graphs.

For natural numbers $a,b$ define $(a,b)$ gadget $G$:

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

Q1: Does $(3,2)$ gadget exist?

Q2: Does $(4,2)$ gadget exist?

To get uniquely hamiltonian regular graph for Q2, take two copies of the gadget $G_1$ and $G_2$. Merge $u_1,u_2$ and $v_1,v_2$.

Likely the answer to Q1 is positive since there are uniquely hamiltonian graphs with minimum degree $3$ and maximum degree $4$, while the answer to Q2 is likely negative since it is conjectured that there are no uniquely hamiltonian $4$-regular graphs.

Both gadgets are regular graph with two edges subdivided once.

Improve this question
$\endgroup$
1

1 Answer 1

Reset to default
1
$\begingroup$

Surely the answer to Q1 is negative. If you found such a graph, then by joining two copies together (joining $u$ in one copy to $u$ in the second, and the same for $v$), would this not give a 3-regular uniquely hamiltonian graph?

Improve this answer
$\endgroup$
1
  • $\begingroup$ This appears to forbid unique hamiltonian path between a lot of vertices in cubic graphs. "Undoing" the subdivisions leaves a cubic graph and just removes the endpoints of the path. Problematic case is distance u-v = 2. $\endgroup$
    – joro
    Commented Feb 6, 2017 at 14:28

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .