MATCHING PRECLUSION FOR ALTERNATING GROUP GRAPHS AND THEIR GENERALIZATIONS
Eddie Cheng, Linda M. Lesniak, Marc J. Lipman, László Lipták · International Journal of Foundations of Computer Science · 2008
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.