Fault-tolerant ring embedding in a star graph with both link andnode failures

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