On the Equivalence of Butterfly Graphs and a Class of Cayley Graphs

Chun-Nan Hung and Lih-Hsing Hsu
Department of Computer and Information Science
National Chiao Tung University
Hsinchu, Taiwan 300, R.O.C.



Ting-Yi Sung
Institute of Information Science
Academia Sinica
Taipei, Taiwan 115, R.O.C.



Chang-Hsiung Tsai
Department of Computer Science and Information Engineering
Dahan Junior College of Engineering and Business
Hualien, Taiwan 971, R.O.C

July 1997

Abstract:

We show that a generalization of the degree-four Cayley graphs defined by P.Vadapalli and P. K. Srimani [1] is in fact isomorphic to generalized butterfly graphs.

In [1], Vadapalli and Srimani proposed a new family of Cayley graphs G_n of constant degree four. We show that this family of graphs is indeed isomorphic to the well-known binary butterfly graph BF_n (also known as wrapped butterfly in [2]). Moreover, we prove that a generalization of G_n, denoted by G(n, d), is isomorphic to the generalized butterfly graph BF(n, d).

Let n be an integer with $n \ge 3$, and $\{a_{1,1}, a_{1,2}, \ldots, a_{1,d}, a_{2,1}, a_{2,2} \ldots, a_{2,d}, \ldots, a_{n,1}, a_{n,2}, \ldots a_{n,d}\}$ be a set of $d \, n$ distinct elements. Let V(G(n, d)) and E(G(n, d)) be the vertex set and edge set of G(n, d), respectively. Each vertex in G(n, d) has an n-bit representation given by $t_{i+1}t_{i+2} \cdots t_nt_1 \cdots t_i$, where $0 \le i \le n - 1$ and $t_k \in \{a_{k,1}, a_{k,2}, \ldots, a_{k,d} \}$ for all $1 \le k \le n$. It is obvious that $\vert V(G(n, d))\vert = n \, d^n$. Function g_j, for every $1 \le j \le d$, is defined on V(G(n, d)) onto itself by assigning

$$g_j(t_{i+1}t_{i+2} \cdots t_nt_1 \cdots t_i) = t_{i+2} \cdots t_nt_1 \cdots t_ia_{i+1,j}$$

Obviously, all g_j are bijective functions. Each vertex $x \in V(G(n, d))$ is linked to exactly 2d vertices g_j(x) and g_j^-1(x), for $1 \le j \le d$. In particular, G(n, 2) is the family of Cayley graphs G_n proposed in [1]. The authors proposed simple and optimal routing algorithms for G_n. Moreover, they showed that G_n has a Hamiltonian cycle, a diameter of $\lfloor\frac{3n}{2}\rfloor$, and connectivity of 4.

The vertex set of BF(n, d), denoted by V(BF(n, d)), is the set given by

$$\{ (b_0b_1 \cdots b_{n-1}, i) \mid \, b_j \in \{0, 1, \ldots... ...0 \le j \le n-1 \hbox{ and } i \in \{0, 1, \ldots, n-1\} \}.$$

It is obvious that $\vert V(BF(n, d))\vert = n \, d^n$. Two vertices $(b_0 b_1 \cdots b_{n-1}, i)$ and $(b^{\prime}_0 b^{\prime}_1 \cdots b^{\prime}_{n-1}, i^{\prime})$ are adjacent in BF(n, d) if and only if $\vert i^{\prime} -i\vert\, ({\bf mod} \, n) = 1$ and $b_j = b^{\prime}_j$ for all $0 \le j \ne i^{\prime} \le n-1$. We can assume without loss of generality that $i^{\prime} = i+1 \, ({\bf mod} \, n)$. The edge set of BF(n, d) is denoted by E(BF(n, d)). In particular, the binary butterfly graph BF_n denotes BF(n, 2). It is known that BF_n is a 4-regular Cayley graph and has a diameter of $\lfloor\frac{3n}{2}\rfloor$. Barth and Raspaud [3] showed that BF_n contains two edge-disjoint Hamiltonian cycles. These properties are similar to those of G_n.

In fact, BF(n, d) is isomorphic to G(n, d) as stated in the following theorem.

Theorem 1

G(n, d) is isomorphic to BF(n, d) for $n \ge 3$.

Proof: Let $(b_0 b_1 \cdots b_{n-1}, i)$ be a node in BF(n, d). We define a function $\pi$ mapping V(BF(n, d)) to V(G(n, d)) as follows:

$$\pi((b_0b_1\cdots b_{n-1},i)) = t_{i+1}t_{i+2} \cdots t_nt_1 \cdots t_i$$

where t_j = a_j,k if b_j-1 = k - 1 for some $1 \le k \le d$. Obviously, the function $\pi$ is a one-to-one correspondence and thus bijective.

Let $u = (b_0b_1 \cdots b_{n-1},i)$ and $v = (b^{\prime}_0b^{\prime}_1 \cdots b^{\prime}_{n-1}, i^{\prime})$ be two vertices in BF(n, d), and $\pi (u) = t_{i+1}t_{i+2}$ $\cdots t_nt_1 \cdots t_i$, $\pi (v) = t^{\prime}_{i^{\prime}+1} t^{\prime}_{i^{\prime}+2} \cdots t^{\prime}_nt^{\prime}_1 \cdots t^{\prime}_{i^{\prime}}$ be two vertices in G(n, d).

Suppose that u and v are adjacent in BF(n, d). We can assume without loss of generality that $i^{\prime} = i + 1 ({\bf mod} \, n)$. It follows that $b_j = b^{\prime}_j$ for all $0 \le j \ne i^{\prime} \le n-1$. That is, $v = (b_0 b_1 \cdots b_{i^{\prime} -1} b^{\prime}_{i^{\prime}} b_{i^{\prime}+1} \cdots b_{n-1}, i^{\prime})$. Then

$$\pi(v) = \begin{array} {ll} t_{i+2}t_{i+3} \cdots t_nt_1... ...ox{when } b^{\prime}_{i^{\prime}} = k - 1. \\ \end{array}$$

Thus $\pi(u)$ and $\pi(v)$ are adjacent in G(n, d). Therefore $(u, v) \in E(BF(n, d))$ implies $(\pi(u), \pi(v)) \in E(G(n, d))$. On the other hand, let $\pi(u), \pi(v)$ be adjacent in G(n, d). It follows that $\pi(v)$ can be $g_j(\pi (u))$ and $g_j^{-1} (\pi (u))$ for all $1 \le j \le d$. Consider $\pi (v) = g_j(\pi (u))$ for any $1 \le j \le d$. It follows that $\pi(v) = t_{i+2}t_{i+3} \cdots t_nt_1 \cdots t_i a_{i+1,j}$. Since $u = (b_0b_1 \cdots b_{n-1},i)$, it follows that $v = (b_0 b_1 \cdots b_i b^*_{i+1} b_{i+2} \cdots b_{n-1}, i+1)$ where b^*_i+1 = j - 1. Thus $\pi (v) = g_j(\pi (u))$ implies $(u, v) \in E(BF(n, d))$. Since every g_j is bijective function, it follows that $\pi(v) = g^{-1}_j(\pi(u))$ also implies $(u, v) \in E(BF(n, d))$. Therefore $(\pi(u), \pi(v)) \in E(G(n, d))$ implies $(u, v) \in E(BF(n, d))$ and furthermore, the theorem follows. $\Box$

Corollary 1

The class of degree four Cayley graphs G_n is isomorphic to the binary butterfly graphs BF_n.

REFERENCES

[1]

P. Vadapalli, and P. K. Srimani ``A new family of Cayley graph interconnection networks of constant degree four," IEEE Transactions on Parallel and Distributed System, vol 7, no 1, pp. 26-32, Jan. 1996.

[2]

F. T. Leighton, Introduction to Parallel Algorithms and Architecture: Arrays, Trees, Hypercubes. Morgan Kaufmann, San Mateo, Chap 3, pp.442-446, 1992.

[3]

D. Barth and A. Raspaud, ``Two disjoint hamiltonian cycles in the butterfly graph," Information Processing Letters, vol 51, no 4, pp. 175-179, Aug. 1994.