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.

(this question is about trying to use some combinatorics to simplify an algorithm and save memory)
Let $K_{2n+1}$ be a complete undirected graph on $2n+1$ vertices. I would like to generate a Eulerian circuit of this graph (visit each edge exactly once).

One solution is to run the DFS-based algorithm that can find a Eulerian circuit in any Eulerian graph (a graph with all vertices of even degree).

However, I'm hoping it's possible to use the nice structure of $K_{2n+1}$ to avoid constructing the graph and running the algorithm. Is there a way to construct one such circuit in O(n) time with O(1) memory?

Motivation: The motivation behind this is an algorithm which receives a list L and needs to calculate $B(A(x), A(y))$ for each unordered pair ${x,y}$ of distinct elements of L (I'm only considering unordered pairs since $B(u,w)=B(w,u)$). The result of operation A is very large and takes almost half of the available memory. Such a circuit will allow me to minimize the number of calls to operation $A$.

Note: This is a sort of "undirected" version of generating a de-Bruijn sequence. I once heard it's possible to generate a de-Bruijn sequence with constant memory, but I don't know how to do that.

share|improve this question

1 Answer 1

up vote 5 down vote accepted

Yes it is possible.

Number the vertices $1,2, \dots 2n+1$.

Consider the sequence $1, 2n, 2, 2n-1, 3, 2n-2, \dots, n,n+1$, ignore $2n+1$ at the moment.

This gives a hamiltonian path in $K_{2n}$.

Now add $1$ to each vertex $\mod 2n$, to get $2,1,3,2n,4, 2n-1 \dots, n+1, n+2$. This can be visualized as writing the numbers $1,2, \dots, 2n$ in a circle and rotating the path. (see figure below).

Repeat this process of adding $1$, $n$ times. This gives you a set of $n$ edge-disjoint hamiltonian paths in $K_{2n}$. (We can show that by proving that (wlog) $1$ is first adjacent to $2n$, then $2,3$, then $4,5$ etc)

To each of these paths, add $2n+1$ at the end and join back to the first vertex of the path.

This gives you an Euler tour of $K_{2n+1}$ which starts and ends at vertex $2n+1$.

This can be computed in constant memory.

Note that this basically follows the (classic/folklore) construction that $K_{2n+1}$ can be decomposed into $n$ edge-disjoint Hamiltonian cycles. See this for instance, Modern Graph Theory, page 16.

In case that book is not accessible, here is a snapshot of the relevant part of that page:

alt text

share|improve this answer

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.