Originator: Brian Alspach (presented by West - REGS 2007)
Definitions: An n-vertex digraph D is circulant if there is a set Q⊆{1,...,n-1} such that vivj∈E(D) if and only if j-i&isin Q when the subscripts are treated modulo n. The values in Q have been called the connection set of D. A decomposition of D is cyclically invariant if each subgraph is obtained from every other by adding a constant to the subscripts. In this problem, a decomposition is also called a factorization.
Question: Does every circulant digraph have a cyclically invariant path factorization?
Comments: The digraph has n|Q| edges, and the decomposition will consist of n paths, each with an edge of each ``length'', in the same order. An obvious necessary condition is that ∑qi is not a multiple of n, though it that case one could ask for a decomposition into invariant cycles.
The question is easy to phrase numerically. Is it true that for every subset Q of [n-1] not summing to a multiple of n, there is a permutation of Q such that no segment (consecutive elements) of the resulting list sums to a multiple of n (except possibly the full list).
Let t=|Q|. The answer is known to be "yes" when t=1 and t=2. It also holds for t=n-1: when n is odd, 1+...+(n-1) is a multiple of n and the necessary condition fails, but when n is even, the permutation 1,n-2,3,n-4,...,4,n-3,2,n-1 gives the desired path. Another approach would be to prove the claim for special values of n.