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.

$\endgroup$
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?

$\endgroup$
  • $\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 Feb 6 '17 at 14:28

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.