Provided existence, what is the smallest graph $G(V,E)$ with two edge-disjoint Hamiltonian paths between $u$ and $v;\ \lbrace u,v\rbrace\subset V$?
$\begingroup$
$\endgroup$
5
asked Jun 2, 2021 at 3:31
-
$\begingroup$ I guess you want to exclude the graph with a unique vertex. In this case the minimal number of vertices is 5 ($K_5$ has two edge-disjoint hamiltonian cycles). It's easy to check that 4 or less is impossible. $\endgroup$– Antoine LabelleCommented Jun 2, 2021 at 3:48
-
$\begingroup$ 5 doesn't suffice; let the first path be A,B,C,D,E then every other Hamilton path between A and E shares an edge with the first one: A,C,D,B,E: (C,D); A,D,B,C,E:(B,C); A,D,C,B,E: (C,D),(B,C); A,C,B,D,E: (BC); A,B,D,C,E: (AB). However 6 vertices are sufficient A,B,C,D,E,F and A,C,E,B,D,F. $\endgroup$– Manfred WeisCommented Jun 2, 2021 at 15:24
-
$\begingroup$ I see, I thought you authorized $u=v$ $\endgroup$– Antoine LabelleCommented Jun 3, 2021 at 4:07
-
$\begingroup$ If you add edges to the smallest solution you preserve hamiltonicity and end with K_n, right? $\endgroup$– joroCommented Jun 3, 2021 at 7:57
-
$\begingroup$ @joro of course adding edges preserves Hamiltonian paths and cycles; a subset relation $A\subseteq B$ remains true when adding elements to $B$; is that interesting? $\endgroup$– Manfred WeisCommented Jun 3, 2021 at 13:05
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
Juust to indicate that there is a solution to the problem: the trivial solution for the smallest graph with $k$ edge-disjoint Hamilton paths between a given pair of vertices is to take a graph $G'$ with $k$ edge-disjoint Hamilton cycles and split one of its vertices.
The smallest graph with two edge-disjoint Hamilton cycles is $K_5$ and so the smallest graph that solves the original problem is a vertex-split $K_5$ depicted below:
answered Jun 2, 2021 at 15:47