Bipancyclic Properties of Faulty Hypercubes

A bipartite graph is bipancyclic if it contains cycles of every even length from 4 to and edge bipancyclic if every edge lies on a cycle of every even length from 4 to . Let denote the -dimensional hypercube. Let be a subset of such that can be decomposed into two parts and , where is a union of disjoint adjacent pairs of , and consists of edges. We prove that is bipancyclic if . Moreover, is edge bipancyclic if with . 1. Introduction Interconnection networks play an important role in parallel computing/communication systems. The graph embedding problem, which is a central issue in evaluating a network, asks if the guest graph is a subgraph of a host graph. A benefit of graph embedding is that we can apply an existing algorithm for guest graphs to host graphs. This problem has attracted a burst of studies in recent years. Note that cycle networks are useful for designing simple algorithms with low communication costs. Thus, there are many studies on the cycle embedding problem. The cycle embedding problem deals with identifying all possible lengths of the cycles in a given graph. For the graph definition and notation, we follow [1]. Let be -bit binary strings. The Hamming weight of , denoted by , is the number of such that . Let and be two -bit binary strings. The Hamming distance between two vertices and is the number of different bits in the corresponding strings of both vertices. The -dimensional hypercube, denoted by , has all -bit binary strings as its vertices; two vertices and are adjacent if and only if . Obviously, is a bipartite graph with bipartition and . A vertex of is white if is odd, otherwise is black. It is known that the distance between and is . For , , let denote the subgraph of induced by . Obviously, is isomorphic to . For any vertex , we use to denote the bit . Moreover, we use to denote the vertex with for and . An edge is of dimension if . The hypercube is one of the most popular interconnection networks for parallel computers/communication systems [2]. This is partly due to its attractive properties, such as regularity, recursive structure, vertex and edge symmetry, maximum connectivity as well as effective routing and broadcasting algorithms. Note that the hypercube is a bipartite graph for every integer . The corresponding cycle embedding problem on bipartite graphs is called the bipancyclic property. A bipartite graph is bipancyclic if it contains cycles of every even length from 4 to , inclusive. There are some variations of the bipancyclic property. A bipartite graph is edge bipancyclic if every edge lies on a cycle of