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., containing 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.
|Number of pages||6|
|Journal||IEEE Symposium on Parallel and Distributed Processing - Proceedings|
|State||Published - 1 Jan 1996|
|Event||Proceedings of the 1996 10th International Parallel Processing Symposium - Honolulu, HI, USA|
Duration: 15 Apr 1996 → 19 Apr 1996