1 Answers
In graph theory, a branch of mathematics, the matching preclusion number of a graph G ] is the minimum number of edges whose deletion results in the destruction of a perfect matching or near-perfect matching. Matching preclusion measures the robustness of a graph as a communications network topology for distributed algorithms that require each node of the distributed system to be matched with a neighboring partner node.
In many graphs, mp is equal to the minimum degree of any vertex in the graph, because deleting all edges incident to a single vertex prevents it from being matched. This set of edges is called a trivial matching preclusion set. A variant definition, the conditional matching preclusion number, asks for the minimum number of edges the deletion of which results in a graph that has neither a perfect or near-perfect matching nor any isolated vertices.
It is NP-complete to test whether the matching preclusion number of a given graph is below a given threshold.
The strong matching preclusion number is a generalization of the matching preclusion number; the SMP number of a graph G, smp is the minimum number of vertices and/or edges whose deletion results in a graph that has neither perfect matchings nor almost-perfect matchings.