Fault-tolerant panconnectivity of augmented cubes

被引：9

作者：

Wang, Hailiang ^{[1
]}

Wang, Jianwei ^{[1
]}

Xu, Jun-Ming ^{[1
]}

机构：

[1] Univ Sci & Technol China, Dept Math, Hefei 230026, Peoples R China

来源：

FRONTIERS OF MATHEMATICS IN CHINA | 2009年 / 4卷 / 04期

基金：

中国国家自然科学基金;

关键词：

Path; pancyclic; hamiltonian connected; panconnectivity; augmented cube; fault tolerance; STAR GRAPHS; SUPER CONNECTIVITY; PANCAKE GRAPHS; VERTEX FAULTS; FREE PATHS; PANCYCLICITY; HAMILTONICITY; HYPERCUBES; EMBEDDINGS;

D O I：

10.1007/s11464-009-0042-4

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

The augmented cube AQ(n) is a variation of the hypercube Q(n). This paper considers the panconnectivity of AQ(n) (n >= 3) with at most 2n-5 faulty vertices and/or edges and shows that, for any two fault-free vertices u and v with distance d in AQ(n), there exist fault-free uv-paths of every length from d + 2 to 2(n) - f - 1, where f is the number of faulty vertices in AQ(n). The proof is based on an inductive construction.

引用

页码：697 / 719

页数：23

共 21 条

[1] Weak-vertex-pancyclicity of (n, k)-star graphs [J].

Chen, Ying-You ;

Duh, Dyi-Rong ;

Ye, Tai-Ling ;

Fu, Jung-Sheng .

THEORETICAL COMPUTER SCIENCE, 2008, 396 (1-3) :191-199

[2]

Choudum S. A., 2003, ELECT NOTES DISCRETE, V15

[3] Augmented cubes [J].

Choudum, SA ;

Sunitha, V .

NETWORKS, 2002, 40 (02) :71-84

[4] Fault-free Hamiltonian cycles in twisted cubes with conditional link faults [J].

Fu, Jung-Sheng .

THEORETICAL COMPUTER SCIENCE, 2008, 407 (1-3) :318-329

[5] Embedding longest fault-free paths onto star graphs with more vertex faults [J].

Hsieh, SY .

THEORETICAL COMPUTER SCIENCE, 2005, 337 (1-3) :370-378

[6] Longest fault-free paths in star graphs with vertex faults [J].

Hsieh, SY ;

Chen, GH ;

Ho, CW .

THEORETICAL COMPUTER SCIENCE, 2001, 262 (1-2) :215-227

[7] Fault hamiltonicity of augmented cubes [J].

Hsu, HC ;

Chiang, LC ;

Tan, JJM ;

Hsu, LH .

PARALLEL COMPUTING, 2005, 31 (01) :131-145

[8] Geodesic pancyclicity and balanced pancyclicity of Augmented cubes [J].

Hsu, Hong-Chun ;

Lai, Pao-Lien ;

Tsai, Chang-Hsiung .

INFORMATION PROCESSING LETTERS, 2007, 101 (06) :227-232

[9] The super connectivity of the pancake graphs and the super laceability of the star graphs [J].

Lin, CK ;

Huang, HM ;

Hsu, LH .

THEORETICAL COMPUTER SCIENCE, 2005, 339 (2-3) :257-271

[10] Fault-tolerant embedding of paths in crossed cubes [J].

Ma, Meijie ;

Liu, Guizhen ;

Xu, Jun-Ming .

THEORETICAL COMPUTER SCIENCE, 2008, 407 (1-3) :110-116

← 1 2 3 →