Ring Embedding in Faulty Star Graphs

Jung-Hwan CHANG  Chan-Su SHIN  Kyung-Yong CHWA  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E82-A   No.9   pp.1953-1964
Publication Date: 1999/09/25
Online ISSN: 
DOI: 
Print ISSN: 0916-8508
Type of Manuscript: PAPER
Category: Graphs and Networks
Keyword: 
graph embedding,  fault tolerance,  star graph,  ring,  

Full Text: PDF>>
Buy this Article



Summary: 
In this paper, we consider the ring embedding problem in faulty star graphs. Our embedding is based on the path transition scheme and node borrow technique in the ring of 4-dimensional substars with evenly distributed faults. Let Sn be the n-dimensional star graph having n! nodes. We will show that a ring of length n! - 2f can be found in Sn when the number of faulty nodes f is at most n-3. In the worst case, the loss of 2f nodes in the size of fault-free ring is inevitable because the star graph is bipartite. In addition, this result is superior to the best previous result that constructs the ring of length n! - 4f under the same fault condition. Moreover, by extending this result into the star graph with both node and edge faults simultaneously, we can find the fault-free ring of length n! - 2 fn in Sn when it contains fn faulty nodes and fe faulty edges such that fn + fe n-3.