Perfect-Matching Preclusion

摘要

The (ptrfect-)matching preclusion number, mp(G), of an n-vertex graph G is the minimum number of edges that must be removed from G in order to ensure that the resultant graph does not have a perfect matching if n is even, or a matching on n — 1 vertices if n is odd. We establish the value of mp(G) for various classes of graphs.