Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
1  
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)? –  hardmath Jul 31 '11 at 13:06
3  
Clearly each vertex is connected to 2, 3 or 4 other vertices. –  Henry Jul 31 '11 at 13:06
    
@hardmath, yes, that would be an example of graph that satisfies the restrictions. –  user8861 Jul 31 '11 at 13:14
add comment

1 Answer

up vote 2 down vote accepted

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.