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 条

[1] Linearly many faults in augmented cubes [J].

Angjeli, Ariana ;

Cheng, Eddie ;

Liptak, Laszlo .

INTERNATIONAL JOURNAL OF PARALLEL EMERGENT AND DISTRIBUTED SYSTEMS, 2013, 28 (05) :475-483

[2] Linearly many faults in dual-cube-like networks [J].

Angjeli, Ariana ;

Cheng, Eddie ;

Liptak, Laszlo .

THEORETICAL COMPUTER SCIENCE, 2013, 472 :1-8

[3]

Bondy J. A, 2008, GRAPH THEORY

[4]

Chartrand G., 1984, Bombay Math. Colloq. Bull., V2, P1

[5] Restricted connectivity for three families of interconnection networks [J].

Chen, Y-Chuang ;

Tan, Jimmy J. M. .

APPLIED MATHEMATICS AND COMPUTATION, 2007, 188 (02) :1848-1855

[6] Increasing the connectivity of the star graphs [J].

Cheng, E ;

Lipman, MJ .

NETWORKS, 2002, 40 (03) :165-169

[7]

CHENG E, 2000, C NUMER, V146, P97

[8]

Cheng E., 2006, CONGR NUMER CONF J N, V180, P81

[9] Fault resiliency of Cayley graphs generated by transpositions [J].

Cheng, Eddie ;

Liptak, Laszlo .

INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE, 2007, 18 (05) :1005-1022

[10] Linearly many faults in Cayley graphs generated by transposition trees [J].

Cheng, Eddie ;

Liptak, Laszlo .

INFORMATION SCIENCES, 2007, 177 (22) :4877-4882

← 1 2 →