Linearly many faults in Cayley graphs generated by transposition trees

被引：99
|
作者：
Cheng, Eddie [1 ]
Liptak, Laszlo [1 ]
机构：
[1] Oakland Univ, Dept Math & Stat, Rochester, MI 48309 USA
来源：
INFORMATION SCIENCES | 2007年 / 177卷 / 22期
关键词：
interconnection networks; star graph; bubble-sort graph; Cayley graphs; transposition tree; superconnectedness;
D O I：
10.1016/j.ins.2007.05.034
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
We prove that when linearly many vertices are deleted in a Cayley graph generated by a transposition tree, the resulting graph has a large connected component containing almost all remaining vertices. (C) 2007 Elsevier Inc. All rights reserved.
引用
收藏
页码：4877 / 4882
页数：6
相关论文
共 49 条
  • [1] Linearly many faults in Cayley graphs generated by transposition triangle free unicyclic graphs
    Li, Peiheng
    Meng, Jixiang
    THEORETICAL COMPUTER SCIENCE, 2020, 847 (847) : 95 - 102
  • [2] Conditional connectivity of Cayley graphs generated by transposition trees
    Yang, Weihua
    Li, Hengzhe
    Meng, Jixiang
    INFORMATION PROCESSING LETTERS, 2010, 110 (23) : 1027 - 1030
  • [3] Orienting Cayley graphs generated by transposition trees
    Cheng, Eddie
    Liptak, Laszlo
    Shawash, Nart
    COMPUTERS & MATHEMATICS WITH APPLICATIONS, 2008, 55 (11) : 2662 - 2672
  • [4] Star structure connectivity of cayley graphs generated by transposition trees
    Kaige Pan
    Dongqin Cheng
    The Journal of Supercomputing, 2023, 79 : 4398 - 4411
  • [5] Star structure connectivity of cayley graphs generated by transposition trees
    Pan, Kaige
    Cheng, Dongqin
    JOURNAL OF SUPERCOMPUTING, 2023, 79 (04) : 4398 - 4411
  • [6] FAULT-TOLERANT MAXIMAL LOCAL-CONNECTIVITY ON CAYLEY GRAPHS GENERATED BY TRANSPOSITION TREES
    Shih, Lun-Min
    Chiang, Chieh-Feng
    Hsu, Lih-Hsing
    Tan, Jimmy J. M.
    JOURNAL OF INTERCONNECTION NETWORKS, 2009, 10 (03) : 253 - 260
  • [7] The Extendability of Cayley Graphs Generated by Transposition Trees
    Feng, Yongde
    Xie, Yanting
    Liu, Fengxia
    Xu, Shoujun
    MATHEMATICS, 2022, 10 (09)
  • [8] Diameters of Cayley graphs generated by transposition trees
    Kraft, Benjamin
    DISCRETE APPLIED MATHEMATICS, 2015, 184 : 178 - 188
  • [9] On the Strictness of a Bound for the Diameter of Cayley Graphs Generated by Transposition Trees
    Ganesan, Ashwin
    MATHEMATICAL MODELLING AND SCIENTIFIC COMPUTATION, 2012, 283 : 54 - 61
  • [10] The spanning cyclability of Cayley graphs generated by transposition trees
    Qiao, Hongwei
    Sabir, Eminjan
    Meng, Jixiang
    DISCRETE APPLIED MATHEMATICS, 2023, 328 : 60 - 69
12345