Embed longest rings onto star graphs with vertex faults

Abstract

The star graph has been recognized as an attractive alternative to the hypercube. Let F/sub e/ and F/sub /spl nu// 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/sub e/|/spl les/n-3 (|F/sub /spl nu//|=0), and a ring of length at least n!-4|F/sub /spl nu//| if |F/sub /spl nu//|/spl les/n-3 (|F/sub 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.