Conditional Fault Hamiltonicity of the Star Graph

Abstract

Fault tolerance is an important property of network performance. A graph $G$ is $k$-edge-fault conditional Hamiltonian if $G–F$ is Hamiltonian for every $F\subset E(G)$ with $|F|\le k$ and $\delta (G–F)\ge 2$. In this paper, we show that for $n\ge 4$, the $n$-dimensional star graph $S_n$ is $(3n–10)$-edge-fault conditional Hamiltonian.