TY - JOUR
T1 - Edge-pancyclicity and path-embeddability of bijective connection graphs
AU - Fan, Jianxi
AU - Jia, Xiaohua
PY - 2008/1/15
Y1 - 2008/1/15
N2 - An n-dimensional Bijective Connection graph (in brief BC graph) is a regular graph with 2n nodes and n2n-1 edges. The n-dimensional hypercube, crossed cube, Möbius 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(Xn, x, y) + 2 ≤ l ≤ 2n - 1 can be embedded between x and y with dilation 1 in Xn for x, y ∈ V(Xn) with x ≠ y in Xn, where Xn (n ≥ 4) is a n-dimensional BC graph satisfying the three specific conditions and V(Xn) is the node set of Xn. Furthermore, by this result, we can claim that Xn is edge-pancyclic. Lastly, we show that these results can be applied to not only crossed cubes and Möbius cubes, but also other BC graphs except crossed cubes and Möbius cubes. So far, the research on edge-pancyclicity and path-embeddability has been limited in some specific interconnection architectures such as crossed cubes, Möbius cubes. © 2007 Elsevier Inc. All rights reserved.
AB - An n-dimensional Bijective Connection graph (in brief BC graph) is a regular graph with 2n nodes and n2n-1 edges. The n-dimensional hypercube, crossed cube, Möbius 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(Xn, x, y) + 2 ≤ l ≤ 2n - 1 can be embedded between x and y with dilation 1 in Xn for x, y ∈ V(Xn) with x ≠ y in Xn, where Xn (n ≥ 4) is a n-dimensional BC graph satisfying the three specific conditions and V(Xn) is the node set of Xn. Furthermore, by this result, we can claim that Xn is edge-pancyclic. Lastly, we show that these results can be applied to not only crossed cubes and Möbius cubes, but also other BC graphs except crossed cubes and Möbius cubes. So far, the research on edge-pancyclicity and path-embeddability has been limited in some specific interconnection architectures such as crossed cubes, Möbius cubes. © 2007 Elsevier Inc. All rights reserved.
KW - Bijective connection graph
KW - Crossed cube
KW - Dilation
KW - Edge-pancyclicity
KW - Graph embedding
KW - Möbius cube
KW - Parallel computing system
KW - Path
UR - http://www.scopus.com/inward/record.url?scp=35348965669&partnerID=8YFLogxK
UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-35348965669&origin=recordpage
U2 - 10.1016/j.ins.2007.08.012
DO - 10.1016/j.ins.2007.08.012
M3 - 21_Publication in refereed journal
VL - 178
SP - 340
EP - 351
JO - Information Sciences
JF - Information Sciences
SN - 0020-0255
IS - 2
ER -