Fault hamiltonicity and fault hamiltonian connectivity of the arrangement graphs

Abstract

The arrangement graph A(n,k) is a generalization of the star graph. There are some results concerning fault Hamiltonicity and fault Hamiltonian connectivity of the arrangement graph. However, these results are restricted in some particular cases and, thus, are less completed. In this paper, we improve these results and obtain a stronger and simpler statement. Let n - k greater than or equal to 2 and F subset of or equal to V(A(n,k)) boolean OR E(A(n,k)). We prove that A(n,k) - F is Hamiltonian if F less than or equal to k(n - k) - 2 and A(n,k) - F is Hamiltonian connected if F less than or equal to k(n - k) - 3. These results are optimal.