TY - JOUR
T1 - Embedding of cycles in twisted cubes with edge-pancyclic
AU - Fan, Jianxi
AU - Jia, Xiaohua
AU - Lin, Xiaola
PY - 2008/7
Y1 - 2008/7
N2 - In this paper, we study the embedding of cycles in twisted cubes. It has been proven in the literature that, for any integer l, 4 ≤ l ≤ 2 n , a cycle of length l can be embedded with dilation 1 in an n-dimensional twisted cube, n ≥ 3. We obtain a stronger result of embedding of cycles with edge-pancyclic. We prove that, for any integer l, 4 ≤ l ≤ 2 n , and a given edge (x,y) in an n-dimensional twisted cube, n ≥ 3, a cycle C of length l can be embedded with dilation 1 in the n-dimensional twisted cube such that (x,y) is in C in the twisted cube. Based on the proof of the edge-pancyclicity of twisted cubes, we further provide an O(llog∈l+n 2+nl) algorithm to find a cycle C of length l that contains (u,v) in TQ n for any (u,v) E(TQ n ) and any integer l with 4 ≤ l ≤ 2 n. © 2007 Springer Science+Business Media, LLC.
AB - In this paper, we study the embedding of cycles in twisted cubes. It has been proven in the literature that, for any integer l, 4 ≤ l ≤ 2 n , a cycle of length l can be embedded with dilation 1 in an n-dimensional twisted cube, n ≥ 3. We obtain a stronger result of embedding of cycles with edge-pancyclic. We prove that, for any integer l, 4 ≤ l ≤ 2 n , and a given edge (x,y) in an n-dimensional twisted cube, n ≥ 3, a cycle C of length l can be embedded with dilation 1 in the n-dimensional twisted cube such that (x,y) is in C in the twisted cube. Based on the proof of the edge-pancyclicity of twisted cubes, we further provide an O(llog∈l+n 2+nl) algorithm to find a cycle C of length l that contains (u,v) in TQ n for any (u,v) E(TQ n ) and any integer l with 4 ≤ l ≤ 2 n. © 2007 Springer Science+Business Media, LLC.
KW - Cycle
KW - Dilation
KW - Edge-pancyclicity
KW - Embedding
KW - Interconnection network
KW - Twisted cube
UR - http://www.scopus.com/inward/record.url?scp=43949119412&partnerID=8YFLogxK
UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-43949119412&origin=recordpage
U2 - 10.1007/s00453-007-9024-7
DO - 10.1007/s00453-007-9024-7
M3 - RGC 21 - Publication in refereed journal
VL - 51
SP - 264
EP - 282
JO - Algorithmica (New York)
JF - Algorithmica (New York)
SN - 0178-4617
IS - 3
ER -