Conditional edge-fault Hamiltonicity of augmented cubes

被引：49

作者：

Hsieh, Sun-Yuan ^{[1
]}

Cian, Yi-Ru ^{[1
]}

机构：

[1] Natl Cheng Kung Univ, Dept Comp Sci & Informat Engn, Tainan 70101, Taiwan

来源：

INFORMATION SCIENCES | 2010年 / 180卷 / 13期

关键词：

Augmented cubes; Fault-tolerant embedding; Graph-theoretic interconnection networks; Hamiltonian cycles; Hamiltonicity; STAR GRAPHS; LONG PATHS; DISJOINT PATHS; CYCLES; HYPERCUBES; LINK; CONNECTIVITY;

D O I：

10.1016/j.ins.2010.03.005

中图分类号：

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

学科分类号：

0812 ;

摘要：

The augmented cube is a variation of hypercubes, it possesses many superior properties. In this paper, we show that, for any n-dimensional augmented cube (n >= 3) with faulty edges up to 4n - 8 in which each vertex is incident to at least two fault-free edges, there exists a fault-free Hamiltonian cycle. Our result is optimal with respect to the number of faulty edges tolerated. (C) 2010 Elsevier Inc. All rights reserved.

引用

页码：2596 / 2617

页数：22

共 44 条

[1] A GROUP-THEORETIC MODEL FOR SYMMETRIC INTERCONNECTION NETWORKS [J].