{{Short description|Robustness of graph perfect matchings}} {{CS1 config|mode=cs2}} thumb|upright=1.2|The '''matching preclusion number''' <math>\mathrm{mp}(G)</math> of the graph <math>G</math> on the left is 2, found by removing a minimum of 2 edges as shown on the right. In graph theory, a branch of mathematics, the '''matching preclusion number''' of a graph <math>G</math>, denoted <math>\mathrm{mp}(G)</math>, is the minimum number of edges whose deletion results in the elimination of all perfect matchings or near-perfect matchings (matchings that cover all but one vertex in a graph with an odd number of vertices).<ref>{{citation | last1 = Brigham | first1 = Robert C. | last2 = Harary | first2 = Frank | author2-link = Frank Harary | last3 = Violin | first3 = Elizabeth C. | last4 = Yellen | first4 = Jay | journal = Congressus Numerantium | pages = 185–192 | publisher = Utilitas Mathematica Publishing, Inc. | title = Perfect-matching preclusion | volume = 174 | year = 2005}}.</ref> Matching preclusion measures the quality 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.<ref name="cl07"/>
In many graphs, <math>\mathrm{mp}(G)</math> 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.<ref name="cl07">{{citation | last1 = Cheng | first1 = Eddie | last2 = Lipták | first2 = László | doi = 10.1002/net.20187 | issue = 2 | journal = Networks | pages = 173–180 | title = Matching preclusion for some interconnection networks | volume = 50 | year = 2007| doi-access = free }}.</ref> 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.<ref>{{citation | last1 = Cheng | first1 = Eddie | last2 = Lesniak | first2 = Linda | last3 = Lipman | first3 = Marc J. | last4 = Lipták | first4 = László | doi = 10.1016/j.ins.2008.10.029 | issue = 8 | journal = Information Sciences | pages = 1092–1101 | title = Conditional matching preclusion sets | volume = 179 | year = 2009}}.</ref><ref>{{citation | last1 = Park | first1 = Jung-Heum | last2 = Son | first2 = Sang Hyuk | doi = 10.1016/j.tcs.2009.02.041 | issue = 27–29 | journal = Theoretical Computer Science | pages = 2632–2640 | title = Conditional matching preclusion for hypercube-like interconnection networks | volume = 410 | year = 2009| doi-access = free }}.</ref>
It is NP-complete to test whether the matching preclusion number of a given graph is below a given threshold.<ref>{{citation |last1 = Lacroix |first1 = Mathieu |last2 = Ridha Mahjoub |first2 = A. |last3 = Martin |first3 = Sébastien |last4 = Picouleau |first4 = Christophe |title = On the NP-completeness of the perfect matching free subgraph problem |journal = Theoretical Computer Science |date = March 2012 |volume = 423 |pages = 25–29 |doi = 10.1016/j.tcs.2011.12.065 }}</ref><ref>{{citation | last1 = Dourado | first1 = Mitre Costa | last2 = Meierling | first2 = Dirk | last3 = Penso | first3 = Lucia D. | last4 = Rautenbach | first4 = Dieter | last5 = Protti | first5 = Fabio | last6 = de Almeida | first6 = Aline Ribeiro | doi = 10.1002/net.21624 | issue = 3 | journal = Networks | pages = 210–213 | title = Robust recoverable perfect matchings | volume = 66 | year = 2015}}.</ref>
The strong matching preclusion number (or simply, SMP number) is a generalization of the matching preclusion number; the SMP number of a graph <math>G</math>, denoted <math>\mathrm{smp}(G)</math>, is the minimum number of vertices and/or edges whose deletion results in a graph that has neither perfect matchings nor almost-perfect matchings.<ref>{{citation | last1 = Mao | first1 = Yaping | last2 = Wang | first2 = Zhao | last3 = Cheng | first3 = Eddie | last4 = Melekian | first4 = Christopher | doi = 10.1016/j.tcs.2017.12.035 | journal = Theoretical Computer Science | pages = 11–20 | title = Strong matching preclusion number of graphs | volume = 713 | year = 2018| doi-access = free }}.</ref>
== Super matched graphs ==
A graph <math>G</math> with an even number of vertices is called '''maximally matched''' if <math>\mathrm{mp}(G) = \delta(G)</math>, where <math>\delta(G)</math> denotes the minimum degree. In such graphs, some trivial matching preclusion set (the edges incident to a vertex of minimum degree) is optimal. A graph is called '''super matched''' if every optimal matching preclusion set is trivial.<ref name="wang2019">{{citation | last1 = Wang | first1 = Zhao | last2 = Melekian | first2 = Christopher | last3 = Cheng | first3 = Eddie | last4 = Mao | first4 = Yaping | doi = 10.1016/j.tcs.2018.06.050 | url = https://www.researchgate.net/publication/326216842_Matching_preclusion_number_in_product_graphs | journal = Theoretical Computer Science | pages = 38–47 | title = Matching preclusion number in product graphs | volume = 755 | year = 2019}}</ref> Every super matched graph is maximally matched, but the converse is not necessarily true.
Being super matched is considered a desirable property for interconnection networks, as it indicates that in the event of random link failures, it is unlikely that all failed links will be incident to a single vertex. Hypercube graphs and their variants are known to be super matched.<ref name="wang2019"/>
== Graph products ==
The matching preclusion number can be bounded for graphs constructed using various graph product operations. For graphs <math>G</math> and <math>H</math> with an even number of vertices:<ref name="wang2019"/>
Cartesian product <math>G \square H</math>:
:<math>\mathrm{mp}(G) + \mathrm{mp}(H) \leq \mathrm{mp}(G \square H) \leq \delta(G) + \delta(H)</math>
If both <math>G</math> and <math>H</math> are super matched, then <math>G \square H</math> is super matched.
Strong product <math>G \boxtimes H</math>:
:<math>\mathrm{mp}(G)\mathrm{mp}(H) + \mathrm{mp}(G) + \mathrm{mp}(H) \leq \mathrm{mp}(G \boxtimes H) \leq \delta(G)\delta(H) + \delta(G) + \delta(H)</math>
If both <math>G</math> and <math>H</math> are super matched with <math>\delta(G) \geq 2</math> and <math>\delta(H) \geq 2</math>, then <math>G \boxtimes H</math> is super matched.
Direct product <math>G \times H</math>:
:<math>\mathrm{mp}(G)\mathrm{mp}(H) \leq \mathrm{mp}(G \times H) \leq \delta(G)\delta(H)</math>
If both <math>G</math> and <math>H</math> are super matched with <math>\delta(G) \geq 2</math> and <math>\delta(H) \geq 2</math>, then <math>G \times H</math> is super matched.
Lexicographic product <math>G \circ H</math>:
:<math>\mathrm{mp}(H) + \mathrm{mp}(G)|V(H)| \leq \mathrm{mp}(G \circ H) \leq \delta(H) + \delta(G)|V(H)|</math>
If <math>G</math> is maximally matched and <math>H</math> is super matched with <math>\delta(H) \geq 2</math>, then <math>G \circ H</math> is super matched.
For other binary graph operations such as the join, corona, and cluster operations, bounds on matching preclusion numbers have also been established, though these operations generally do not preserve the super matched property.<ref name="wang2019"/>
== Fractional matching preclusion ==
A '''fractional matching''' is a function <math>f</math> that assigns to each edge a number in <math>[0,1]</math> such that <math>\sum_{e \sim v} f(e) \leq 1</math> for each vertex <math>v</math>, where the sum is taken over all edges incident with <math>v</math>. A '''fractional perfect matching''' is a fractional matching <math>f</math> satisfying <math>\sum_{e \sim v} f(e) = 1</math> for every vertex <math>v \in V(G)</math>. Clearly, a perfect matching is also a fractional perfect matching, but the converse is not necessarily true.<ref name="zou2022">{{citation | last1 = Zou | first1 = Jinyu | last2 = Mao | first2 = Yaping | last3 = Wang | first3 = Zhao | last4 = Cheng | first4 = Eddie | doi = 10.1016/j.dam.2022.01.014 | arxiv = 1909.07878 | journal = Discrete Applied Mathematics | pages = 142–153 | title = Fractional matching preclusion number of graphs | volume = 311 | year = 2022}}</ref>
The '''fractional matching preclusion number''' of a graph <math>G</math>, denoted <math>\mathrm{fmp}(G)</math>, is the minimum number of edges whose deletion results in a graph that has no fractional perfect matching.<ref name="zou2022"/> For any graph <math>G</math> of order <math>n</math>,
:<math>0 \leq \mathrm{fmp}(G) \leq n-1</math>
with both bounds being sharp. For graphs with an even number of vertices, the fractional matching preclusion number is bounded by the ordinary matching preclusion number:
:<math>\mathrm{mp}(G) \leq \mathrm{fmp}(G) \leq \delta(G)</math>
where <math>\delta(G)</math> denotes the minimum degree. In particular, if <math>G</math> is a graph with an even number of vertices and <math>\mathrm{mp}(G) = \delta(G)</math>, then <math>\mathrm{fmp}(G) = \mathrm{mp}(G) = \delta(G)</math>.<ref name="zou2022"/>
For complete graphs <math>K_n</math> with <math>n \geq 7</math>, the fractional matching preclusion number equals <math>\mathrm{fmp}(K_n) = n-1</math>. More generally, for graphs with an even order <math>n \geq 4k+6</math>, <math>\mathrm{fmp}(G) = n-k</math> if and only if <math>\delta(G) = n-k</math>.
== Integer ''k''-matching preclusion ==
As a generalization of matching preclusion, the concept of '''integer <math>k</math>-matching preclusion''' extends the analysis to integer <math>k</math>-matchings.<ref name="chang2024">{{citation | last1 = Chang | first1 = Caibing | last2 = Liu | first2 = Yan | doi = 10.1051/ro/2024064 | arxiv = 2306.01216 | journal = RAIRO Operations Research | pages = 5369–5380 | title = Integer k-matching preclusion of graphs | volume = 58 | year = 2024}}</ref> An '''integer <math>k</math>-matching''' of a graph <math>G</math> is a function <math>h: E(G) \to {0, 1, \ldots, k}</math> such that <math>\sum_{e \in \Gamma(v)} h(e) \leq k</math> for any vertex <math>v \in V(G)</math>, where <math>\Gamma(v)</math> denotes the set of edges incident with <math>v</math>. An integer <math>k</math>-matching is '''perfect''' if <math>\sum_{e \in \Gamma(v)} h(e) = k</math> for each vertex <math>v</math>, and '''almost-perfect''' if there exists exactly one vertex <math>v'</math> such that <math>\sum_{e \in \Gamma(v')} h(e) = k-1</math> and all other vertices satisfy the perfect condition. Note that integer 1-matching coincides with the standard definition of matching.
The '''integer <math>k</math>-matching preclusion number''', denoted <math>\mathrm{mp}_k(G)</math>, is the minimum number of edges whose deletion results in a graph that has neither a perfect nor an almost-perfect integer <math>k</math>-matching. The '''strong integer <math>k</math>-matching preclusion number''', denoted <math>\mathrm{smp}_k(G)</math>, is the minimum number of vertices and/or edges whose deletion results in a graph that has neither a perfect nor an almost-perfect integer <math>k</math>-matching. By definition, <math>\mathrm{mp}_1(G) = \mathrm{mp}(G)</math> and <math>\mathrm{smp}_1(G) = \mathrm{smp}(G)</math>.<ref name="chang2024"/>
For even values of <math>k</math>, the integer <math>k</math>-matching preclusion number equals the fractional matching preclusion number, since a graph has a perfect fractional matching if and only if it has a perfect integer <math>k</math>-matching when <math>k</math> is even. Additionally, every graph has no almost-perfect integer <math>k</math>-matching for even <math>k</math>. Therefore, analysis typically focuses on odd values of <math>k \geq 3</math>.<ref name="chang2024"/>
=== Results for specific graph families ===
For complete graphs <math>K_n</math> with <math>n \geq 6</math>,
:<math>\mathrm{mp}_k(K_n) = \mathrm{smp}_k(K_n) = n-1</math> for odd <math>k \geq 3</math>.
For smaller complete graphs, the values differ slightly: :<math>\mathrm{mp}_k(K_3) = \mathrm{smp}_k(K_3) = 1</math>, <math>\mathrm{mp}_k(K_4) = 3</math> while <math>\mathrm{smp}_k(K_4) = 2</math>, and <math>\mathrm{mp}_k(K_5) = \mathrm{smp}_k(K_5) = 3</math>.<ref name="chang2024"/>
For bipartite graphs <math>G</math>, the relationship between integer <math>k</math>-matching and ordinary matching is particularly simple: the integer <math>k</math>-matching number equals <math>k</math> times the matching number, i.e., <math>\mu_k(G) = k\mu(G)</math>. This implies that if <math>G</math> is a bipartite graph with an odd number of vertices, then
:<math>\mathrm{mp}_k(G) = \mathrm{smp}_k(G) = 0</math>,
while for even bipartite graphs,
:<math>\mathrm{mp}_k(G) = \mathrm{mp}(G)</math> and <math>\mathrm{smp}_k(G) \leq \mathrm{smp}(G)</math>.<ref name="chang2024"/>
For arrangement graphs <math>A_{n,s}</math> (a class of interconnection network topologies), when <math>3 \leq s \leq n-2</math>, the strong integer <math>k</math>-matching preclusion number equals <math>\mathrm{smp}k(A{n,s}) = s(n-s)</math>, which is the minimum degree of the graph. For the special case <math>A_{n,2}</math> with <math>n \geq 5</math>, <math>\mathrm{smp}k(A{n,2}) = 2n-4</math>.<ref name="chang2024"/>
== Related concepts ==
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, the minimum number of edges to delete in order to eliminate all cycles.
== References == {{reflist}}
Category:Graph invariants Category:Matching (graph theory)