In graph theory, a branch of mathematics, the matching preclusion number of a graph G {\displaystyle G} , denoted m p ( G ) {\displaystyle \mathrm {mp} (G)} , 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). 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. In many graphs, m p ( G ) {\displaystyle \mathrm {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 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 {\displaystyle G} , denoted s m p ( G ) {\displaystyle \mathrm {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.
Super matched graphs A graph G {\displaystyle G} with an even number of vertices is called maximally matched if m p ( G ) = δ ( G ) {\displaystyle \mathrm {mp} (G)=\delta (G)} , where δ ( G ) {\displaystyle \delta (G)} 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. 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.
Graph products The matching preclusion number can be bounded for graphs constructed using various graph product operations. For graphs G {\displaystyle G} and H {\displaystyle H} with an even number of vertices: Cartesian product G ◻ H {\displaystyle G\square H} :
m p ( G ) + m p ( H ) ≤ m p ( G ◻ H ) ≤ δ ( G ) + δ ( H ) {\displaystyle \mathrm {mp} (G)+\mathrm {mp} (H)\leq \mathrm {mp} (G\square H)\leq \delta (G)+\delta (H)}
If both G {\displaystyle G} and H {\displaystyle H} are super matched, then G ◻ H {\displaystyle G\square H} is super matched. Strong product G ⊠ H {\displaystyle G\boxtimes H} :
m p ( G ) m p ( H ) + m p ( G ) + m p ( H ) ≤ m p ( G ⊠ H ) ≤ δ ( G ) δ ( H ) + δ ( G ) + δ ( H ) {\displaystyle \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)}
If both G {\displaystyle G} and H {\displaystyle H} are super matched with δ ( G ) ≥ 2 {\displaystyle \delta (G)\geq 2} and δ ( H ) ≥ 2 {\displaystyle \delta (H)\geq 2} , then G ⊠ H {\displaystyle G\boxtimes H} is super matched. Direct product G × H {\displaystyle G\times H} :
m p ( G ) m p ( H ) ≤ m p ( G × H ) ≤ δ ( G ) δ ( H ) {\displaystyle \mathrm {mp} (G)\mathrm {mp} (H)\leq \mathrm {mp} (G\times H)\leq \delta (G)\delta (H)}
… excerpt ends here. Continue reading the full article.
