Fault tolerance in the arrangement graphs

Let n and k   be positive integers with n−k⩾1n−k⩾1. The arrangement graph An,kAn,k is recognized as an attractive interconnection network. Let fmfm be the minimum number of faulty vertices that make every sub-arrangement graph An−m,k−mAn−m,k−m faulty in An,kAn,k under vertex-failure model. In this paper, we prove that f0=1f0=1, f1=nf1=n, fn−2=n!/2fn−2=n!/2, and n!/(n−m)!⩽fm⩽(k−1m−1)n!/(n−m)!−2(k−2m−1)n!/(n−m+1)! for 2⩽m⩽k−12⩽m⩽k−1.