Fault Hamiltonicity and fault Hamiltonian connectivity of the (n, k)‐star graphs
Hong-Chun Hsu, Yi‐Lin Hsieh, Jimmy J.M. Tan, Lih‐Hsing Hsu · Networks · 2003
Abstract In this paper, we consider the fault Hamiltonicity, and the fault Hamiltonian connectivity of the (n, k)‐star graph Sn,k. Assume that F ⊂ V(Sn,k) ∪ E(Sn,k). For n − k ≥ 2, we prove that Sn,k − F is Hamiltonian if |F| ≤ n − 3 and Sn,k − F is Hamiltonian connected if |F| ≤ n − 4. For n − k = 1, Sn,n−1 is isomorphic to the n‐star graph Sn which is known to be Hamiltonian if and only if n > 2 and Hamiltonian connected if and only if n = 2. Moreover, all the bounds are tight. © 2003 Wiley Periodicals, Inc.