### Abstract

The star graph interconnection network has been recognized as an attractive alternative to the hypercube network. Previously, the star graph has been shown to contain a Hamiltonian cycle. In this paper, we consider an injured star graph with some faulty links and nodes. We show that even with f _{e} ≤ n - 3 faulty links, a Hamiltonian cycle still can be found in an n-star, and that with f _{v} ≤ n - 3 faulty nodes, a ring containing at most 4f _{v} nodes less than that in a Hamiltonian cycle can be found (i.e., the ring contains at least n! - 4f _{v} nodes). In general, in an n-star with f _{e} faulty links and f _{v} faulty nodes, where f _{e} + f _{v} ≤ n - 3, our embedding is able to establish a ring containing at least n! - 4f _{v} nodes.

Original language | English |
---|---|

Pages (from-to) | 1185-1195 |

Number of pages | 11 |

Journal | IEEE Transactions on Parallel and Distributed Systems |

Volume | 8 |

Issue number | 12 |

DOIs | |

State | Published - 1 Dec 1997 |

### Keywords

- Fault tolerance
- Graph embedding
- Hamiltonian cycle
- Interconnection network
- Processor allocation
- Ring
- Star graph

## Fingerprint Dive into the research topics of 'Fault-tolerant ring embedding in a star graph with both link and node failures'. Together they form a unique fingerprint.

## Cite this

*IEEE Transactions on Parallel and Distributed Systems*,

*8*(12), 1185-1195. https://doi.org/10.1109/71.640010