Fault Hamiltonicity and fault Hamiltonian connectivity of the (n, k)-star graphs

Abstract

In this paper, we consider the fault Hamiltonicity, and the fault Hamiltonian connectivity of the (n, k)-star graph S-n,S-k. Assume that F subset of V(S-n,S-k) boolean OR E(S-n,S-k). For n - k greater than or equal to 2, we prove that S-n,S-k - F is Hamiltonian if F less than or equal to n - 3 and S-n,S-k - F is Hamiltonian connected if F less than or equal to n - 4. For n - k = 1, S-n,S-n-1 is isomorphic to the n-star graph S-n 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. (C) 2003 Wiley Periodicals, Inc.