Hamilton circuits in the directed wrapped Butterfly network Original Research Article

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