Edge-bipancyclicity of star graphs with faulty elements

被引:15
作者
Huang, Chao-Wen [2 ]
Huang, Hui-Ling [3 ]
Hsieh, Sun-Yuan [1 ]
机构
[1] Natl Cheng Kung Univ, Dept Comp Sci & Informat Engn, Tainan 701, Taiwan
[2] Natl Ctr High Performance Comp, Taichung Branch, Taichung 40763, Taiwan
[3] So Taiwan Univ, Dept Informat Management, Tainan 710, Taiwan
关键词
Cayley graphs; Edge-bipancyclicity; Fault-tolerant embedding; Interconnection networks; Star graphs; FREE PATHS; HAMILTONIAN-LACEABILITY; PANCYCLICITY; HYPERCUBES; CYCLES;
D O I
10.1016/j.tcs.2011.09.006
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
In this paper, we investigate the fault-tolerant edge-bipancyclicity of an n-dimensional star graph S. Given a set F comprised of faulty vertices and/or edges in S, with vertical bar F vertical bar <= n - 3 and any fault-free edge e in S-n - F, we show that there exist cycles of every even length from 6 to n! - 2 vertical bar F-v vertical bar in S-n - F containing e, where n >= 3. Our result is optimal because the star graph is both bipartite and regular with the common degree n - 1. The length of the longest fault-free cycle in the bipartite S-n is n! - 2 vertical bar F-v vertical bar in the worst case, where all faulty vertices are in the same partite set. We also provide some sufficient conditions from which longer cycles with length from n! - 2 vertical bar F-v vertical bar + 2 to n! - 2 vertical bar F-v vertical bar can be embedded. (C) 2011 Elsevier B.V. All rights reserved.
引用
收藏
页码:6938 / 6947
页数:10
相关论文
共 37 条
[1]  
Akers S. B., 1987, Proceedings of the 1987 International Conference on Parallel Processing, P393
[2]   A GROUP-THEORETIC MODEL FOR SYMMETRIC INTERCONNECTION NETWORKS [J].
AKERS, SB ;
KRISHNAMURTHY, B .
IEEE TRANSACTIONS ON COMPUTERS, 1989, 38 (04) :555-566
[3]  
Akl S.G., 1997, Parallel Computation: Models and Methods
[4]   A ROUTING AND BROADCASTING SCHEME ON FAULTY STAR GRAPHS [J].
BAGHERZADEH, N ;
NASSIF, N ;
LATIFI, S .
IEEE TRANSACTIONS ON COMPUTERS, 1993, 42 (11) :1398-1402
[5]  
Bermond J.C., 1992, Discrete Applied Mathematics, V37
[6]  
Bondy J.A., 1971, Journal of Combinatorial Theory, Series B, V11, P80
[7]  
Chang JH, 1999, IEICE T FUND ELECTR, VE82A, P1953
[8]   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
[9]   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
[10]   Hamiltonian path embedding and pancyclicity on the Mobius cube with faulty nodes and faulty edges [J].
Hsieh, Sun-Yuan ;
Chang, Nai-Wen .
IEEE TRANSACTIONS ON COMPUTERS, 2006, 55 (07) :854-863