For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Ring Embedding in Faulty Star Graphs
Jung-Hwan CHANG Chan-Su SHIN Kyung-Yong CHWA
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 1999/09/25
Print ISSN: 0916-8508
Type of Manuscript: PAPER
Category: Graphs and Networks
graph embedding, fault tolerance, star graph, ring,
Full Text: PDF(699.6KB)>>
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.