Imagine I have a graph $G$ with a set of $N$ vertices $(v_1, ..., v_N) \in V$, and $M$ edges $(e_1, ..., e_M) \in E$. This graph has the special property that there exists at least two Hamiltonian cycles, i.e. two distinct orderings of the graph's $N$ vertices, such that each edge in the graph, $e_i$, is traversed by at least one of the two tours.

Furthermore, while it is not necessary that the two Hamiltonian cycles are edge-disjoint, it must always be possible to direct both tours such that no edge is ever traversed in the same direction. In other words, if a directed version of one tour travels from vertex $v_a$ --> $v_b$ (for some arbitrary $a$ and $b$, where $1 \leq a,b \leq N$), the other tour may travel from vertex $v_b$ --> $v_a$ but not from $v_a$ --> $v_b$.

Provided the above specifications, can we say anything general about the connectivity or number of edges/vertices in $G$? Can the above pair of directed Hamiltonian cycles be guaranteed to exist for some family of graphs, and is there a more efficient way to find them than exhaustive search?

Note - This is a reformulation of an earlier question that I decided to take some additional time to think about. To those who read the earlier version, I apologize for any inconvenience.

  • 1
    $\begingroup$ Is an example of what you ask about a cycle $C_N$, on which you have a Hamiltonian cycle and its reverse directed cycle (so that each edge is traversed in opposite directions by both paths)? $\endgroup$ – hardmath Jul 31 '11 at 13:06
  • 3
    $\begingroup$ Clearly each vertex is connected to 2, 3 or 4 other vertices. $\endgroup$ – Henry Jul 31 '11 at 13:06
  • $\begingroup$ @hardmath, yes, that would be an example of graph that satisfies the restrictions. $\endgroup$ – user8861 Jul 31 '11 at 13:14

We may characterize such graphs as follows. Take a permutation $\pi$ of $1 \ldots N$ such that $\pi(j+1) \ne \pi(j)+1$ for all $j$ ($N+1$ being identified as 1 here and below). Then the graph consists of vertices $1 \ldots N$ with edges $\{i,i+1\}$ and $\{\pi_i, \pi_{i+1}\}$ for $i = 1 \ldots N$. The number of edges is $2N - k$ where $k$ is the number of $i$ for which $\pi_{i+1} + 1 = \pi_{i}$.


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.