Mutually independent hamiltonian cycles of binary wrapped butterfly graphs

Abstract

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 G be a graph with N vertices. A hamiltonian cycle C of G is represented by < u(1),u(2),...,u(N),u(1)> to emphasize the order of vertices on C. Two hamiltonian cycles of G, namely C(1) = < u(1),u(2),...,u(N),u(1)> and C(2) = < v(1),v(2),...,v(N),v(1)>, are said to be independent if u(1) = v(1) and u(i) not equal v(i) for all 2 <= i <= N. A collection of m hamiltonian cycles C(1),...,C(m), starting from the same vertex, are m-mutually independent if any two different hamiltonian cycles are independent. The mutually independent hamiltonicity of a graph G, denoted by IHC(G), is defined to be the maximum integer m such that, for each vertex u of G, there exists a set of m-mutually independent hamiltonian cycles starting from u. Let BF(n) denote the n-dimensional binary wrapped butterfly graph. Then we prove that IHC(BF(n)) = 4 for all n >= 3. (C) 2008 Elsevier Ltd. All rights reserved.