Annex C - Abstract
------------------

Title: Hamilton circuits in the directed wrapped Butterfly network
Authors: BERMOND, Jean-Claude and DARROT, Eric and DELMAS, Olivier and
PERENNES, Stphane


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 D. Barth. We also conjecture that
WBF(d,n) (digraph) 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 the conjecture for d prime and n=2. Then, we give
such a Hamilton decomposition for all primes less than 12000 by a
clever computer search, and so, as a corollary, we have a Hamilton
decomposition of WBF(d,n) (digraph) for any d divisible by a number q,
with 4 <= q <= 12000.

Key-words: Butterfly graph, graph theory, Hamilton decomposition,
Hamilton cycle, Hamilton circuit, perfect matching.


Annexe C - Rsum
-----------------

Titre: Circuits Hamiltoniens dans le rseau Butterfly orient
Auteurs: BERMOND, Jean-Claude and DARROT, Eric and DELMAS, Olivier and
PERENNES, Stphane


Dans cet article, nous prouvons que le graphe Butterfly reboucl (dans
sa version orient) WBF(d,n) de degr d et de dimension n contient au
moins d-1circuits Hamiltoniens arc-disjoints, rpondant  une
conjecture de D. Barth. Nous conjecturons aussi que WBF(d,n) (graphe
orient) peut tre dcompos en d circuits Hamiltoniens, sauf pour
{d=2 et n=2}, {d=2 et n=3} et {d=3 et n=2}. Nous montrons qu'il suffit
de prouver cette conjecture pour d premier et n=2. Puis nous donnons
une telle dcomposition pour tous les premiers jusqu' 12000 grce 
une subtilit de programmation, induisant comme corollaire que
WBF(d,n) (graphe orient) admet une dcomposition Hamiltonienne pour
tout d divisible par un nombre q tel que 4 <= q <= 12000.

Mots cls: graphe Butterfly, Thorie des graphes, dcomposition
Hamiltonienne, cycle Hamiltonien, circuit Hamiltonien, couplage
parfait.
