Linearly many faults in Cayley graphs generated by transposition triangle free unicyclic graphs

被引：5
作者：
Li, Peiheng [1 ]
Meng, Jixiang [1 ]
机构：
[1] Xinjiang Univ, Coll Math & Syst Sci, Urumqi 830046, Peoples R China
来源：
THEORETICAL COMPUTER SCIENCE | 2020年 / 847卷
关键词：
Modified bubble-sort graphs; Unicyclic graphs; Cayley graphs; Transposition graphs; Triangle free; CONNECTIVITY;
D O I：
10.1016/j.tcs.2020.09.042
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
We consider a kind of Cayley graphs, including the modified bubble-sort graphs MBn the Cayley graphs generated by lollipop graphs H-n,H-n-1 and the other Cayley graphs generated by unicyclic triangle free graphs. We get that if we delete linearly many vertices in Cayley graphs generated by transposition unicyclic triangle free graphs, then the resulting graphs has a large connected component that comprises of nearly all residual vertices. (C) 2020 Elsevier B.V. All rights reserved.
引用
收藏
页码：95 / 102
页数：8
相关论文
共 20 条
[11]   A strong connectivity property of the generalized exchanged hypercube [J].
Cheng, Eddie ;
Qiu, Ke ;
Shen, Zhizhang .
DISCRETE APPLIED MATHEMATICS, 2017, 216 :529-536
[12]   Connectivity Results of Complete Cubic Networks as Associated with Linearly Many Faults [J].
Cheng, Eddie ;
Qiu, Ke ;
Shen, Zhizhang .
JOURNAL OF INTERCONNECTION NETWORKS, 2015, 15 (1-2)
[13]   Cyclic Vertex-Connectivity of Cayley Graphs Generated by Transposition Trees [J].
Cheng, Eddie ;
Liptak, Laszlo ;
Qiu, Ke ;
Shen, Zhizhang .
GRAPHS AND COMBINATORICS, 2013, 29 (04) :835-841
[14]   Linearly many faults in arrangement graphs [J].
Cheng, Eddie ;
Liptak, Laszlo ;
Yuan, Allen .
NETWORKS, 2013, 61 (04) :281-289
[15]   Matching preclusion and conditional matching preclusion for regular interconnection networks [J].
Cheng, Eddie ;
Lipman, Marc J. ;
Liptak, Laszlo .
DISCRETE APPLIED MATHEMATICS, 2012, 160 (13-14) :1936-1954
[16]   Linearly Many Faults in 2-Tree-Generated Networks [J].
Cheng, Eddie ;
Liptak, Laszlo ;
Sala, Fred .
NETWORKS, 2010, 55 (02) :90-98
[17]  
Gu M.M., 2019, COMPUT J
[18]   On the maximal connected component of a hypercube with faulty vertices III [J].
Yang, XF ;
Evans, DJ ;
Megson, GM .
INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS, 2006, 83 (01) :27-37
[19]   LINEARLY MANY FAULTS IN (n, k)-STAR GRAPHS [J].
Yuan, Allen ;
Cheng, Eddie ;
Liptak, Laszlo .
INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE, 2011, 22 (07) :1729-1745
[20]   Reliability analysis of bijective connection networks in terms of the extra edge-connectivity [J].
Zhang, Mingzu ;
Meng, Jixiang ;
Yang, Weihua ;
Tian, Yingzhi .
INFORMATION SCIENCES, 2014, 279 :374-382
12