Acta mathematica scientia,Series A ›› 2004, Vol. 24 ›› Issue (2): 168-176.

• Articles • Previous Articles     Next Articles

The Fault Tolerant Analysis of Star Graph Interconnection Network

 NIE Xiao-Dong, LIU Hong-Mei, XU Jun-Ming   

  • Online:2004-04-27 Published:2004-04-27
  • Supported by:

    国家自然科学基金项目(10301031及10271114)资助

Abstract:

The restricted connectivity and the restricted fault diam eter are two reliability measures for interconnection networks, in which the aut hors assume that all the neighbors of a vertex do not fail at the same time. In  this paper, the authors show the uniqueness of minimal (vertex) separating set s and of minimal restricted separating sets in the star graphs. The authors present that for the n star graph S_n, its restricted connectivity is 2n -4 and its restricted fault diameter is |_3(n-1)/2_|+2 and n≥7 and |_3(n-1)/2_|+3 for n=4,6, i.e., its fault diameter plus one.

Key words: Star graph, Connectivity, Fault tolerance, Restricted co nnectivity, Restricted fault diameter, Separating set

CLC Number: 

  • 05C05
Trendmd