Embedding cycles of various lengths into star graphs with both edge and vertex faults

摘要

The n-dimensional star graph Sn is an attractive alternative to the hypercube graph and is a bipartite graph with two partite sets of equal size. Let Fv and Fe be the sets of faulty vertices and faulty edges of Sn, respectively. We prove that Sn − Fv − Fe contains a fault-free cycle of every even length from 6 to n! − 2∣Fv∣ with ∣Fv∣ + ∣Fe∣ ⩽ n − 3 for every n ⩾ 4. We also show that Sn − Fv − Fe contains a fault-free path of length n! − 2∣Fv∣ − 1 (respectively, n! − 2∣Fv∣ − 2) between two arbitrary vertices of Sn in different partite sets (respectively, the same partite set) with ∣Fv∣ + ∣Fe∣ ⩽ n − 3 for every n ⩾ 4.