The search functionality is under construction.

The search functionality is under construction.

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 *S*_{n} be the *n*-dimensional star graph having *n*! nodes. We will show that a ring of length *n*! - 2*f* can be found in *S*_{n} when the number of faulty nodes *f* is at most *n*-3. In the worst case, the loss of 2*f* 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*! - 4*f* 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 *f*_{n} in *S*_{n} when it contains *f*_{n} faulty nodes and *f*_{e} faulty edges such that *f*_{n} + *f*_{e} *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

The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.

Copy

Jung-Hwan CHANG, Chan-Su SHIN, Kyung-Yong CHWA, "Ring Embedding in Faulty Star Graphs" in IEICE TRANSACTIONS on Fundamentals,
vol. E82-A, no. 9, pp. 1953-1964, September 1999, doi: .

Abstract: 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 *S*_{n} be the *n*-dimensional star graph having *n*! nodes. We will show that a ring of length *n*! - 2*f* can be found in *S*_{n} when the number of faulty nodes *f* is at most *n*-3. In the worst case, the loss of 2*f* 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*! - 4*f* 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 *f*_{n} in *S*_{n} when it contains *f*_{n} faulty nodes and *f*_{e} faulty edges such that *f*_{n} + *f*_{e} *n*-3.

URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e82-a_9_1953/_p

Copy

@ARTICLE{e82-a_9_1953,

author={Jung-Hwan CHANG, Chan-Su SHIN, Kyung-Yong CHWA, },

journal={IEICE TRANSACTIONS on Fundamentals},

title={Ring Embedding in Faulty Star Graphs},

year={1999},

volume={E82-A},

number={9},

pages={1953-1964},

abstract={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 *S*_{n} be the *n*-dimensional star graph having *n*! nodes. We will show that a ring of length *n*! - 2*f* can be found in *S*_{n} when the number of faulty nodes *f* is at most *n*-3. In the worst case, the loss of 2*f* 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*! - 4*f* 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 *f*_{n} in *S*_{n} when it contains *f*_{n} faulty nodes and *f*_{e} faulty edges such that *f*_{n} + *f*_{e} *n*-3.

keywords={},

doi={},

ISSN={},

month={September},}

Copy

TY - JOUR

TI - Ring Embedding in Faulty Star Graphs

T2 - IEICE TRANSACTIONS on Fundamentals

SP - 1953

EP - 1964

AU - Jung-Hwan CHANG

AU - Chan-Su SHIN

AU - Kyung-Yong CHWA

PY - 1999

DO -

JO - IEICE TRANSACTIONS on Fundamentals

SN -

VL - E82-A

IS - 9

JA - IEICE TRANSACTIONS on Fundamentals

Y1 - September 1999

AB - 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 *S*_{n} be the *n*-dimensional star graph having *n*! nodes. We will show that a ring of length *n*! - 2*f* can be found in *S*_{n} when the number of faulty nodes *f* is at most *n*-3. In the worst case, the loss of 2*f* 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*! - 4*f* 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 *f*_{n} in *S*_{n} when it contains *f*_{n} faulty nodes and *f*_{e} faulty edges such that *f*_{n} + *f*_{e} *n*-3.

ER -