In
graph theory
In mathematics, graph theory is the study of '' graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conn ...
, 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 destruction of a
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 , a perfect matching in is a subset of edge set , such that every vertex in the vertex set is adjacent to exactly ...
or near-perfect matching (a matching that covers 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
A telecommunications network is a group of nodes interconnected by telecommunications links that are used to exchange messages between the nodes. The links may use a variety of technologies based on the methodologies of circuit switching, mes ...
topology for
distributed algorithms 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
Degree may refer to:
As a unit of measurement
* Degree (angle), a unit of angle measurement
** Degree of geographical latitude
** Degree of geographical longitude
* Degree symbol (°), a notation used in science, engineering, and mathemati ...
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
In computational complexity theory, a problem is NP-complete when:
# it is a problem for which the correctness of each solution can be verified quickly (namely, in polynomial time) and a brute-force search algorithm can find a solution by tryin ...
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
In graph theory, a connected graph is -edge-connected if it remains connected whenever fewer than edges are removed.
The edge-connectivity of a graph is the largest for which the graph is -edge-connected.
Edge connectivity and the enumeration ...
, the minimum number of edges to delete in order to disconnect the graph, and the
cyclomatic number, the minimum number of edges to delete in order to eliminate all cycles.
References
Graph invariants
Matching (graph theory)
{{combin-stub