Optimal fault-tolerant Hamiltonicity of star graphs with conditional edge faults

The star graph is viewed as an attractive alternative to the hypercube. In this paper, we investigate the Hamiltonicity of an n-dimensional star graph. We show that for any n-dimensional star graph (n ≥ 4) with at most 3n-10 faulty edges in which each node is incident with at least two fault-free edges, there exists a fault-free Hamiltonian cycle. Our result improves on the previously best known result for the case where the number of tolerable faulty edges is bounded by 2n-7. We also demonstrate that our result is optimal with respect to the worst case scenario, where every other node of a cycle of length 6 is incident with exactly n-3 faulty noncycle edges.