3
$\begingroup$

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.

  • 0
    @hardmath, yes, that would be an example of graph that satisfies the restrictions.2011-07-31

1 Answers 1

2

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