In
graph theory
In mathematics and computer science, graph theory is the study of ''graph (discrete mathematics), graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of ''Vertex (graph ...
, a branch of mathematics, the matching preclusion number of a graph ''G'' (denoted mp(''G'')) is the minimum number of edges whose deletion results in the elimination of all
perfect matching
In graph theory, a perfect matching in a graph is a matching that covers every vertex of the graph. More formally, given a graph with edges and vertices , a perfect matching in is a subset of , such that every vertex in is adjacent to exact ...
s or near-perfect matchings (matchings that cover all but one vertex in a graph with an odd number of vertices). Matching preclusion measures the robustness of a graph as a
communications network topology for
distributed algorithm A distributed algorithm is an algorithm designed to run on computer hardware constructed from interconnected processors. Distributed algorithms are used in different application areas of distributed computing, such as telecommunications, scientifi ...
s that require each node of the distributed system to be matched with a neighboring partner node.
In many graphs, mp(''G'') is equal to the minimum
degree of any vertex in the graph, because deleting all edges incident to a single vertex prevents that vertex 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
In computational complexity theory, NP-complete problems are the hardest of the problems to which ''solutions'' can be verified ''quickly''.
Somewhat more precisely, a problem is NP-complete when:
# It is a decision problem, meaning that for any ...
to test whether the matching preclusion number of a given graph is below a given threshold.
The strong matching preclusion number (or simply, SMP number) is a generalization of the matching preclusion number; the SMP number of a graph ''G'', smp(''G'') is the minimum number of vertices and/or edges whose deletion results in a graph that has neither perfect matchings nor almost-perfect matchings.
[.]
Other numbers defined in a similar way by edge deletion in an undirected graph include the
edge connectivity, the minimum number of edges to delete in order to disconnect the graph, and the
cyclomatic number
In graph theory, a branch of mathematics, the cyclomatic number, circuit rank, cycle rank, or nullity of an undirected graph is the minimum number of edges that must be removed from the graph to break all its cycles, making it into a tree or fo ...
, the minimum number of edges to delete in order to eliminate all cycles.
References
Graph invariants
Matching (graph theory)
{{graph-stub