MATCHING PRECLUSION FOR ALTERNATING GROUP GRAPHS AND THEIR GENERALIZATIONS
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 the alternating group graphs, Cayley graphs generated by 2-trees and the (n, k)-arrangement graphs. Moreover, we classify all the optimal solutions.
alternating group graphs perfect matching cayley graphs interconnection networks arrangement graphs