Dihedral Butterfly Digraph and Its Cayley Graph Representation

Haruaki ONISHI  Yuuki TANAKA  Yukio SHIBATA  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E91-A   No.2   pp.613-622
Publication Date: 2008/02/01
Online ISSN: 1745-1337
DOI: 10.1093/ietfec/e91-a.2.613
Print ISSN: 0916-8508
Type of Manuscript: PAPER
Category: Graphs and Networks
butterfly digraph,  dihedral butterfly digraph,  Cayley graph,  wreath product,  

Full Text: PDF>>
Buy this Article

In this paper, we present a new extension of the butterfly digraph, which is known as one of the topologies used for interconnection networks. The butterfly digraph was previously generalized from binary to d-ary. We define a new digraph by adding a signed label to each vertex of the d-ary butterfly digraph. We call this digraph the dihedral butterfly digraph and study its properties. Furthermore, we show that this digraph can be represented as a Cayley graph. It is well known that a butterfly digraph can be represented as a Cayley graph on the wreath product of two cyclic groups [1]. We prove that a dihedral butterfly digraph can be represented as a Cayley graph in two ways.