Hamilton Circuits in the Directed Butterfly Network - Archive ouverte HAL Access content directly
Reports Year : 1996

## Hamilton Circuits in the Directed Butterfly Network

Jean-Claude Bermond
Eric Darrot
• Function : Author
Olivier Delmas
Stéphane Pérennes
• Function : Author
• PersonId : 942945

#### Abstract

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

#### Domains

Computer Science [cs] Other [cs.OH]

### Dates and versions

inria-00073773 , version 1 (24-05-2006)

### Identifiers

• HAL Id : inria-00073773 , version 1

### Cite

Jean-Claude Bermond, Eric Darrot, Olivier Delmas, Stéphane Pérennes. Hamilton Circuits in the Directed Butterfly Network. RR-2925, INRIA. 1996. ⟨inria-00073773⟩

### Export

BibTeX TEI Dublin Core DC Terms EndNote Datacite

106 View