Edge-Fault-Tolerant Pancyclicity of Alternating Group Graphs

被引：6

作者：

Tsai, Ping-Ying ^{[1
]}

Chen, Gen-Huey ^{[1
]}

Fu, Jung-Sheng ^{[2
]}

机构：

[1] Natl Taiwan Univ, Dept Comp Sci & Informat Engn, Taipei 10764, Taiwan

[2] Natl United Univ, Dept Elect Engn, Miaoli, Taiwan

来源：

NETWORKS | 2009年 / 53卷 / 03期

关键词：

alternating group graph; Cayley graph; cycle embedding; fault tolerance; pancycle; INTERCONNECTION NETWORKS; HAMILTONIAN-CONNECTIVITY; AUGMENTED CUBES; STAR GRAPHS; N-CUBES; PANCONNECTIVITY; CYCLES;

D O I：

10.1002/net.20291

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

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. Previously, the alternating group graph was shown to be pancyclic, i.e., containing cycles of all possible lengths. In this article, we further show that the alternating group graph remains pancyclic, even if there are up to 2n - 6 edge faults, where n >= 3 is the dimension of the alternating group graph. The result is optimal with respect to the number of edge faults tolerated. (C) 2009 Wiley Periodicals, Inc. NETWORKS, Vol. 53(3), 307-313 2009

引用

页码：307 / 313

页数：7

共 50 条

[21] Embedding Hamiltonian cycles in alternating group graphs under conditional fault model
Tsai, Ping-Ying
Fu, Jung-Sheng
Chen, Gen-Huey
INFORMATION SCIENCES, 2009, 179 (06) : 851 - 857
[22] A Complete Fault Tolerant Method for Extra Fault Diagnosability of Alternating Group Graphs
Lin, Limei
Huang, Yanze
Xu, Li
Hsieh, Sun-Yuan
IEEE TRANSACTIONS ON RELIABILITY, 2021, 70 (03) : 957 - 969
[23] Edge-fault-tolerant strong Menger edge connectivity of bubble-sort star graphs
Guo, Jia
Lu, Mei
DISCRETE APPLIED MATHEMATICS, 2021, 297 (297) : 109 - 119
[24] Edge-fault-tolerant edge-bipancyclicity of balanced hypercubes
Li, Pingshan
Xu, Min
APPLIED MATHEMATICS AND COMPUTATION, 2017, 307 : 180 - 192
[25] Bipanconnectivity and edge-fault-tolerant bipancyclicity of hypercubes
Li, TK
Tsai, CH
Tan, JJM
Hsu, LH
INFORMATION PROCESSING LETTERS, 2003, 87 (02) : 107 - 110
[26] An optimal result on fault-tolerant cycle-embedding in alternating group graphs
Xue, Zhan-jun
Liu, San-yang
INFORMATION PROCESSING LETTERS, 2009, 109 (21-22) : 1197 - 1201
[27] Fault-Tolerant Cycle Embedding in Cartesian Product Graphs: Edge-Pancyclicity and Edge-Bipancyclicity with Faulty Edges
Cheng, Chia-Wen
Hsieh, Sun-Yuan
IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, 2015, 26 (11) : 2997 - 3011
[28] The Edge-Fault-Tolerant Bipancyclicity of the Even k-ary n-cube
Fang, Jywe-Fei
COMPUTER JOURNAL, 2011, 54 (02): : 255 - 262
[29] Enabling high fault-tolerant embedding capability of alternating group graphs
Zhuang, Hongbin
Li, Xiao-Yan
Wang, Dajin
Lin, Cheng-Kuan
Zhao, Kun
FUTURE GENERATION COMPUTER SYSTEMS-THE INTERNATIONAL JOURNAL OF ESCIENCE, 2024, 158 : 110 - 121
[30] Edge-fault-tolerant hamiltonicity of locally twisted cubes under conditional edge faults
Hsieh, Sun-Yuan
Wu, Chang-Yu
JOURNAL OF COMBINATORIAL OPTIMIZATION, 2010, 19 (01) : 16 - 30

← 1 2 3 4 5 →