Fault-Tolerant Panconnectivity of Augmented Cubes AQn

被引：8

作者：

Xu, Xirong ^{[1
]}

Zhang, Huifeng ^{[1
]}

Zhang, Sijia ^{[2
]}

Yang, Yuansheng ^{[1
]}

机构：

[1] Dalian Univ Technol, Sch Comp Sci & Technol, Dalian 116024, Peoples R China

[2] Dalian Ocean Univ, Sch Informat Engn, Dalian 116023, Peoples R China

来源：

INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE | 2019年 / 30卷 / 08期

基金：

国家重点研发计划;

关键词：

Augmented cubes; path; embedding; panconnectivity; fault tolerance; EMBEDDING MESHES; GEODESIC-PANCYCLICITY; BINARY-TREES; PATHS; CYCLES; HAMILTONICITY; CONNECTIVITY;

D O I：

10.1142/S0129054119500254

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

The augmented cube AQ(n) is a variation of the hypercube Q(n). This paper considers the fault-tolerant Panconnectivity of AQ(n). Assume that F subset of V (AQ(n))[E(AQ(n)) and n >= 4. We prove that for any two fault-free vertices u and v with distance d in AQn, there exists a fault-free path P-uv of each length from max{d+2, 4} to 2(n) - f(v) - 1 in AQ(n) - F if vertical bar F vertical bar <= 2(n) - 4, where f(v) is the number of faulty vertices in AQ(n). Moreover, the bound is sharp.

引用

页码：1247 / 1278

页数：32

共 38 条

[1] Edge disjoint Hamiltonian cycles in k-ary n-cubes and hypercubes
Bae, MM
Bose, B
[J]. IEEE TRANSACTIONS ON COMPUTERS, 2003, 52 (10) : 1271 - 1284
[2] Bondy J., 1976, GRAPH THEORY APPL, V377, P170
[3] Geodesic-pancyclicity and fault-tolerant panconnectivity of augmented cubes
Chan, Hung-Chang
Chang, Jou-Ming
Wang, Yue-Li
Horng, Shi-Jinn
[J]. APPLIED MATHEMATICS AND COMPUTATION, 2009, 207 (02) : 333 - 339
[4] The distinguishing number of the augmented cube and hypercube powers
Chan, Melody
[J]. DISCRETE MATHEMATICS, 2008, 308 (11) : 2330 - 2336
[5] Fault-tolerant cycle-embedding in alternating group graphs
Chang, Jou-Ming
Yang, Jinn-Shyong
[J]. APPLIED MATHEMATICS AND COMPUTATION, 2008, 197 (02) : 760 - 767
[6] Choudum S. A., 2001, TECHNICAL REPORT
[7] Choudum S. A., 2000, TECHNICAL REPORT
[8] Choudum S. A., 2003, ELECT NOTES DISCRETE, V15
[9] Augmented cubes
Choudum, SA
Sunitha, V
[J]. NETWORKS, 2002, 40 (02) : 71 - 84
[10] Edge-pancyclicity and path-embeddability of bijective connection graphs
Fan, Jianxi
Jia, Xiaohua
[J]. INFORMATION SCIENCES, 2008, 178 (02) : 340 - 351

← 1 2 3 4 →