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) less than or equal to n - 3 faulty links, a Hamiltonian cycle still can be found in an n-star, and that with f(v) less than or equal to 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 nl - 4f(v) nodes). In general, in an n-star with f(e) faulty links and f(v) faulty nodes, where f(e) + f(v) less than or equal to n - 3, our embedding is able to establish a ring containing at least nl - 4f(v) nodes.
關聯:
IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS
