Super Connectivity of Component-Composition Networks

被引：0
作者：
Yang, Ming-Chien [1 ]
机构：
[1] Aletheia Univ, Dept Informat Applicat, Tainan 721, Taiwan
来源：
3RD INTERNATIONAL CONFERENCE ON APPLIED COMPUTING AND INFORMATION TECHNOLOGY (ACIT 2015) 2ND INTERNATIONAL CONFERENCE ON COMPUTATIONAL SCIENCE AND INTELLIGENCE (CSI 2015) | 2015年
关键词：
reliability; super connectivity; component-composition networks; fault-tolerance; multiprocessor systems; interconnection networks; PANCAKE GRAPHS; CUBES;
D O I：
10.1109/ACIT-CSI.2015.56
中图分类号：
TP18 [人工智能理论];
学科分类号：
081104 ; 0812 ; 0835 ; 1405 ;
摘要：
The reliability of an interconnection network is an important issue for multiprocessor systems. The super connectivity is a novel measure for the reliability of an interconnection network. Given a graph G, the super connectivity of G is the minimum cardinality of vertices whose removal results in a disconnected graph that contains no isolated vertex. This paper studies the super connectivity of component-composition networks, which includes burnt pancake graphs, star graphs, bubble-sort graphs, pancake graphs, hypercube-like graphs, and so on. We also apply the obtained result for the component-composition networks to determine the super connectivity of various known networks. For instance, we determine that the super connectivity of the n-dimensional burnt pancake graph BPn is 2n - 2 for n >= 2.
引用
收藏
页码：274 / 277
页数：4
相关论文
共 18 条
[1]  
Boesch F., 1989, IEEE T COMPUT, V38, P1586
[2]   SYNTHESIS OF RELIABLE NETWORKS - A SURVEY [J].
BOESCH, FT .
IEEE TRANSACTIONS ON RELIABILITY, 1986, 35 (03) :240-246
[3]   (t, k)-Diagnosis for Component-Composition Graphs under the MM☆ Model [J].
Chen, Chun-An ;
Hsieh, Sun-Yuan .
IEEE TRANSACTIONS ON COMPUTERS, 2011, 60 (12) :1704-1717
[4]   ON COMPUTING A CONDITIONAL EDGE-CONNECTIVITY OF A GRAPH [J].
ESFAHANIAN, AH ;
HAKIMI, SL .
INFORMATION PROCESSING LETTERS, 1988, 27 (04) :195-199
[5]   Super connectivity of Kronecker products of graphs [J].
Guo, Litao ;
Qin, Chengfu ;
Guo, Xiaofeng .
INFORMATION PROCESSING LETTERS, 2010, 110 (16) :659-661
[6]   Longest fault-free paths in star graphs with edge faults [J].
Hsieh, SY ;
Chen, GH ;
Ho, CW .
IEEE TRANSACTIONS ON COMPUTERS, 2001, 50 (09) :960-971
[7]   Ring embedding in faulty pancake graphs [J].
Hung, CN ;
Hsu, HC ;
Liang, KY ;
Hsu, LH .
INFORMATION PROCESSING LETTERS, 2003, 86 (05) :271-275
[8]   Fault-tolerant routing in burnt pancake graphs [J].
Iwasaki, Tatsuya ;
Kaneko, Keiichi .
INFORMATION PROCESSING LETTERS, 2010, 110 (14-15) :535-538
[9]   Edge-bipancyclicity and edge-fault-tolerant bipancyclicity of bubble-sort graphs [J].
Kikuchi, Yosuke ;
Araki, Toru .
INFORMATION PROCESSING LETTERS, 2006, 100 (02) :52-59
[10]   On super edge-connectivity of Cartesian product graphs [J].
Lu, Min ;
Chen, Guo-Liang ;
Xu, Jun-Ming .
NETWORKS, 2007, 49 (02) :152-157
12