Embed longest rings onto star graphs with vertex faults

The star graph has been recognized as an attractive alternative to the hypercube. Let F_e and F_ν be the sets of vertex faults and edge faults, respectively. Previously, Tseng et al. showed that an n-dimensional star graph can embed a ring of length n! if |F_e|⩽n-3 (|F_ν|=0), and a ring of length at least n!-4|F_ν| if |F_ν|⩽n-3 (|F_e |=0). Since an n-dimensional star graph is regular of degree n-1 and is bipartite with two partite sets of equal size, our result achieves optimality in the worst case