Mutually independent hamiltonian cycles of binary wrapped butterfly graphs

Effective utilization of communication resources is crucial for improving performance in multiprocessor/communication systems. In this paper, the mutually independent hamiltonicity is addressed for its effective utilization of resources on the binary wrapped butterfly graph. Let GG be a graph with NN vertices. A hamiltonian cycle CC of GG is represented by 〈u1,u2,…,uN,u1〉〈u1,u2,…,uN,u1〉 to emphasize the order of vertices on CC. Two hamiltonian cycles of GG, namely C1=〈u1,u2,…,uN,u1〉C1=〈u1,u2,…,uN,u1〉 and C2=〈v1,v2,…,vN,v1〉C2=〈v1,v2,…,vN,v1〉, are said to be independent if u1=v1u1=v1 and ui≠viui≠vi for all 2≤i≤N2≤i≤N. A collection of mm hamiltonian cycles C1,…,CmC1,…,Cm, starting from the same vertex, are mm-mutually independent if any two different hamiltonian cycles are independent. The mutually independent hamiltonicity of a graph GG, denoted by IHC(G)IHC(G), is defined to be the maximum integer mm such that, for each vertex uu of GG, there exists a set of mm-mutually independent hamiltonian cycles starting from uu. Let BF(n)BF(n) denote the nn-dimensional binary wrapped butterfly graph. Then we prove that IHC(BF(n))=4IHC(BF(n))=4 for all n≥3n≥3.