Hyper hamiltonian laceability on edge fault star graph

被引：70

作者：

Li, TK ^{[1
]}

Tar, JJM

Hsu, LH

机构：

[1] Ching Yun Univ, Dept Comp Sci & Informat Engn, Jhongli 320, Taiwan

[2] Natl Chiao Tung Univ, Dept Comp & Informat Sci, Hsinchu 300, Taiwan

来源：

INFORMATION SCIENCES | 2004年 / 165卷 / 1-2期

关键词：

star graph; hamiltonian laceable; strongly hamiltonian laceable; hyper hamiltonian laceable; fault tolerant;

D O I：

10.1016/j.ins.2003.09.023

中图分类号：

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

学科分类号：

0812 ;

摘要：

The star graph posses many nice topological properties. Edge fault tolerance is an important issue for a network since the edges in the network may fail sometimes. In this paper, we show that the n-dimensional star graph is (n - 3)-edge fault tolerant hamiltonian laceable, (n - 3)-edge fault tolerant strongly hamiltonian laceable, and (n - 4)-edge fault tolerant hyper hamiltonian laceable. All these results are optimal in a sense described in this paper. (C) 2003 Elsevier Inc. All rights reserved.

引用

页码：59 / 71

页数：13

共 20 条

[1]

Akers S. B., 1986, Proceedings of the 1986 International Conference on Parallel Processing (Cat. No.86CH2355-6), P216

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

AKERS, SB ;

KRISHNAMURTHY, B .

IEEE TRANSACTIONS ON COMPUTERS, 1989, 38 (04) :555-566

[3] Embedding an arbitrary binary tree into the star graph [J].

Bagherzadeh, N ;

Dowd, M ;

Nassif, N .

IEEE TRANSACTIONS ON COMPUTERS, 1996, 45 (04) :475-481

[4] Optimal information dissemination in star and pancake networks [J].

Berthome, P ;

Ferreira, A ;

Perennes, S .

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, 1996, 7 (12) :1292-1300

[5]

BONDY JA, 1982, USR MURTY GRAPH THEO

[6] A COMPARATIVE-STUDY OF TOPOLOGICAL PROPERTIES OF HYPERCUBES AND STAR GRAPHS [J].

DAY, K ;

TRIPATHI, A .

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, 1994, 5 (01) :31-38

[7] A PARALLEL ALGORITHM FOR COMPUTING FOURIER-TRANSFORMS ON THE STAR GRAPH [J].

FRAGOPOULOU, P ;

AKL, SG .

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, 1994, 5 (05) :525-531

[8] OPTIMAL COMMUNICATION ALGORITHMS ON STAR GRAPHS USING SPANNING TREE CONSTRUCTIONS [J].

FRAGOPOULOU, P ;

AKL, SG .

JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING, 1995, 24 (01) :55-71

[9] Fault-free Hamiltonian cycles in faulty arrangement graphs [J].

Hsieh, SY ;

Chen, GH ;

Ho, CW .

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, 1999, 10 (03) :223-237

[10]

Hsieh SY, 2000, NETWORKS, V36, P225, DOI 10.1002/1097-0037(200012)36:4<225::AID-NET3>3.0.CO

← 1 2 →