TY - GEN
T1 - Cycle embedding in alternating group graphs with faulty elements
AU - Tsai, Ping Ying
AU - Lin, Yu Tzu
N1 - Publisher Copyright:
© Springer Science+Business Media Dordrecht 2014.
PY - 2014
Y1 - 2014
N2 - The alternating group graph, which belongs to the class of Cayley graphs, is one of the most versatile interconnection networks for parallel and distributed computing. Cycle embedding is an important issue in evaluating the efficiency of interconnection networks. In this paper, we show that an n-dimensional alternating group graph AGn has the following results, where F is the set of faulty vertices and/or faulty edges in AGn : (1) For n ≥ 4, AGn-F is edge 4-pancyclic if |F| ≤ n − 4; and (2) For n ≥ 3, AGn-F is vertex-pancyclic if |F| ≤ n − 3. All the results are optimal with respect to the number of faulty elements tolerated, and they are improvements over the cycle embedding properties of alternating group graphs proposed previously in several articles.
AB - The alternating group graph, which belongs to the class of Cayley graphs, is one of the most versatile interconnection networks for parallel and distributed computing. Cycle embedding is an important issue in evaluating the efficiency of interconnection networks. In this paper, we show that an n-dimensional alternating group graph AGn has the following results, where F is the set of faulty vertices and/or faulty edges in AGn : (1) For n ≥ 4, AGn-F is edge 4-pancyclic if |F| ≤ n − 4; and (2) For n ≥ 3, AGn-F is vertex-pancyclic if |F| ≤ n − 3. All the results are optimal with respect to the number of faulty elements tolerated, and they are improvements over the cycle embedding properties of alternating group graphs proposed previously in several articles.
KW - Alternating group graph
KW - Cayley graph
KW - Cycle embedding
KW - Fault-tolerant
KW - Interconnection network
KW - Pancyclicity
UR - http://www.scopus.com/inward/record.url?scp=84958042849&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84958042849&partnerID=8YFLogxK
U2 - 10.1007/978-94-007-7262-5_145
DO - 10.1007/978-94-007-7262-5_145
M3 - Conference contribution
AN - SCOPUS:84958042849
SN - 9789400772618
T3 - Lecture Notes in Electrical Engineering
SP - 1281
BT - Advanced Technologies, Embedded and Multimedia for Human-Centric Computing, HumanCom and EMC 2013
PB - Springer Verlag
T2 - Advanced Technologies, Embedded and Multimedia for Human-Centric Computing, HumanCom and EMC 2013
Y2 - 23 August 2013 through 25 August 2013
ER -