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 条
  • [31] Panconnectivity, fault-tolerant Hamiltonicity and Hamiltonian-connectivity in alternating group graphs
    Chang, JM
    Yang, JS
    NETWORKS, 2004, 44 (04) : 302 - 310
  • [32] Edge Fault Tolerant Pancyclicity of the WK-Recursive Network
    Huang, Chien-Hung
    Liu, Yu-Chin
    Liang, Wen-Yew
    Chan, Chen-Yu
    Fang, Jywe-Fei
    2009 IEEE PACIFIC RIM CONFERENCE ON COMMUNICATIONS, COMPUTERS AND SIGNAL PROCESSING, VOLS 1 AND 2, 2009, : 268 - 273
  • [33] Conditional edge-fault-tolerant Hamiltonicity of dual-cubes
    Chen, Jheng-Cheng
    Tsai, Chang-Hsiung
    INFORMATION SCIENCES, 2011, 181 (03) : 620 - 627
  • [34] Geodesic-pancyclicity and fault-tolerant panconnectivity of augmented cubes
    Chan, Hung-Chang
    Chang, Jou-Ming
    Wang, Yue-Li
    Horng, Shi-Jinn
    APPLIED MATHEMATICS AND COMPUTATION, 2009, 207 (02) : 333 - 339
  • [35] Fault-tolerant edge-pancyclicity of locally twisted cubes
    Xu, Xirong
    Zhai, Wenhua
    Xu, Jun-Ming
    Deng, Aihua
    Yang, Yuansheng
    INFORMATION SCIENCES, 2011, 181 (11) : 2268 - 2277
  • [36] The High Faulty Tolerant Capability of the Alternating Group Graphs
    Zhang, Hui
    Hao, Rong-Xia
    Qin, Xiao-Wen
    Lin, Cheng-Kuan
    Hsieh, Sun-Yuan
    IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, 2023, 34 (01) : 225 - 233
  • [37] Fault-tolerant pancyclicity of augmented cubes
    Wang, Wei-Wei
    Ma, Mei-Jie
    Xu, Jun-Ming
    INFORMATION PROCESSING LETTERS, 2007, 103 (02) : 52 - 56
  • [38] Edge-fault-tolerant strong Menger edge connectivity on the class of hypercube-like networks
    Li, Pingshan
    Xu, Min
    DISCRETE APPLIED MATHEMATICS, 2019, 259 : 145 - 152
  • [39] A kind of conditional fault tolerance of alternating group graphs
    Zhang, Zhao
    Xiong, Wei
    Yang, Weihua
    INFORMATION PROCESSING LETTERS, 2010, 110 (22) : 998 - 1002
  • [40] A note on an optimal result on fault-tolerant cycle-embedding in alternating group graphs
    Tsai, Ping-Ying
    INFORMATION PROCESSING LETTERS, 2011, 111 (08) : 375 - 378
12345