Hamilton Circuits in the Directed Butterfly Network

In this paper, we prove that the wrapped Butterfly digraph $\vec{{\cal WBF}}(d,n)$ of degree $d$ and dimension $n$ contains at least $d-1$ arc-disjoint Hamilton circuits, answering a conjecture of D. Barth. We also conjecture that $\vec{{\cal WBF}}(d,n)$ can be decomposed into $d$ Hamilton circuits, except for $d=2$ $n=2$, $d=2$ $n=3$ and $d=3$ $n=2$ . We show that it suffices to prove the conjecture for $d$ prime and $n=3D2$. Then, we give such a Hamilton decomposition for all primes less than 12000 by a clever computer search, and so, as corollary, we have a Hamilton decomposition of $\vec{{\cal WBF}}(d,n)$ for any $d$ divisible by a number $q$, with $4 \leq q \leq 12000$.