Edge-pancyclicity and path-embeddability of bijective connection graphs

An n-dimensional Bijective Connection graph (in brief BC graph) is a regular graph with 2(n) nodes and n2(n-1) edges. The n-dimensional hypercube, crossed cube, Mobius cube, etc. are some examples of the n-dimensional BC graphs. In this paper, we propose a general method to study the edge-pancyclicity and path-embeddability of the BC graphs. First, we prove that a path of length l with dist(X-n, x, y) + 2 <= l <= 2(n) - 1 can be embedded between x and y with dilation 1 in X-n for x,y epsilon V(X-n) with x not equal y in X-n, where X-n (n >= 4) is a n-dimensional BC graph satisfying the three specific conditions and V(X-n) is the node set of X-n. Furthermore, by this result, we can claim that X-n is edge-pancyclic. Lastly, we show that these results can be applied to not only crossed cubes and Mobius cubes, but also other BC graphs except crossed cubes and Mobius cubes. So far, the research on edge-pancyclicity and path-embeddability has been limited in some specific interconnection architectures such as crossed cubes, Mobius cubes. (c) 2007 Elsevier Inc. All rights reserved.