Edge-fault-tolerant pancyclicity of arrangement graphs

被引：10

作者：

Sun, Sainan ^{[1
]}

Xu, Min ^{[1
]}

Wang, Kaishun ^{[1
]}

机构：

[1] Beijing Normal Univ, Sch Math Sci, Minist Educ, Lab Math & Complex Syst, Beijing 100875, Peoples R China

来源：

INFORMATION SCIENCES | 2014年 / 285卷

关键词：

Arrangement graph; Edge-fault-tolerance; Pancyclicity; Hamiltonian; Hamiltonian connected; STAR GRAPHS; HAMILTONIAN CONNECTIVITY; FREE PATHS; BIPANCYCLICITY; HYPERCUBES; CYCLES;

D O I：

10.1016/j.ins.2014.06.046

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

The arrangement graph A(n,k) is a well-known interconnection network. Day and Tripathi proved that A(n,k) is pancyclic for n - k >= 2. In this paper, we improve this result, and we demonstrate that A(n,k) is also pancyclic even if it has no more than (k(n-k) - 2) faulty edges for n - k >= 2. Our result is optimal concerning the edge fault-tolerance. (C) 2014 Elsevier Inc. All rights reserved.

引用

页码：50 / 62

页数：13

共 25 条

[1]

Akers S. B., 1987, Proceedings of the 1987 International Conference on Parallel Processing, P393

[2] EDGE-PANCYCLIC BLOCK-INTERSECTION GRAPHS [J].