The search functionality is under construction.
The search functionality is under construction.

Ring Embedding in Faulty Star Graphs

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

  • Full Text Views

    0

  • Cite this

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.

Publication
IEICE TRANSACTIONS on Fundamentals Vol.E82-A No.9 pp.1953-1964
Publication Date
1999/09/25
Publicized
Online ISSN
DOI
Type of Manuscript
PAPER
Category
Graphs and Networks

Authors

Keyword