Abstract The star graph proposed by Akers et al. (Proc Int Conf Parallel Process, University Park, PA, 1987, pp. 393–400) has many advantages over the n‐cube. However, it suffers from having large gaps in the possible number of vertices. The arrangement graph was proposed by Day and Tripathi (Inf Process Lett 42 (1992), 235–241) to address this issue. Since it is a generalization of the star graph, it retains many of the nice properties of the star graph. In fact, it also generalizes the alternating group graph (Jwo et al., Networks 23 (1993), 315–326). There are many different measures of structural integrity of interconnection networks. In this article, we prove results of the following type for the arrangement graph: If h(r,n,k) vertices are deleted from the arrangement graph An,k, the resulting graph will either be connected or have a large component and small components having at most r − 1 vertices in total. Our result is tight for r ≤ 3, and it is asymptotically tight for r ≥ 4. Moreover, we also determine the cyclic vertex‐connectivity of the arrangement graph. © 2012 Wiley Periodicals, Inc. NETWORKS, 2013

Abstract The matching preclusion number of a graph is the minimum number of edges whose deletion results in a graph that has neither perfect matchings nor almost‐perfect matchings. For many interconnection networks, the optimal sets are precisely those induced by a single vertex. Recently, the conditional matching preclusion number of a graph was introduced to look for obstruction sets beyond those induced by a single vertex. This number is defined to be the minimum number of edges whose deletion results in a graph with no isolated vertices that has neither perfect matchings nor almost‐perfect matchings. In this article, we prove general results regarding the matching preclusion number and the conditional matching preclusion number as well as the classification of their respective optimal sets for bipartite graphs. © 2011 Wiley Periodicals, Inc. NETWORKS, 2011

Abstract The matching preclusion number of a graph with an even number of vertices is the minimum number of edges whose deletion results in a graph that has no perfect matchings. For many interconnection networks, the optimal sets are precisely those induced by a single vertex. It is natural to look for obstruction sets beyond those induced by a single vertex. The conditional matching preclusion number of a graph is the minimum number of edges whose deletion results in a graph with no isolated vertices that has no perfect matchings. In this companion paper of Cheng et al. (Networks (NET 1554)), we find these numbers for a number of popular interconnection networks including hypercubes, star graphs, Cayley graphs generated by transposition trees and hyper‐stars. © 2011 Wiley Periodicals, Inc. NETWORKS, 2011

Abstract In this article we consider a class of Cayley graphs that are generated by certain 3‐cycles on the alternating group An. These graphs are generalizations of the alternating group graph AGn. We look at the case when the 3‐cycles form a “tree‐like structure,” and analyze its fault resiliency. We present a number of structural theorems and prove that even with linearly many vertices deleted, the remaining graph has a large connected component containing almost all vertices. © 2009 Wiley Periodicals, Inc. NETWORKS, 2010

Abstract The matching preclusion number of a graph is the minimum number of edges whose deletion results in a graph that has neither perfect matchings nor almost‐perfect matchings. In this paper, we find this number for various classes of interconnection networks and classify all the optimal solutions. © 2007 Wiley Periodicals, Inc. NETWORKS, Vol. 50(2), 173–180 2007