Conditional fault-tolerant hamiltonicity of star graphs

The star graph possesses many nice topological properties. In this study, we show that for any n-dimensional star graph (n ⩾ 4) with ⩽2n − 7 edge faults in which each node is incident to at least two non-faulty edges, there exists a fault-free Hamiltonian cycle. Compared with the corresponding study in hypercube, our method is rather succinct. Additionally, we also show the probability that an n dimensional star graph with arbitrary 2n − 7 faulty edges at most is Hamiltonian is very close to one.