Matching preclusion

In graph theory, 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 or near-perfect matching (a matching that covers all but one vertex in a graph with an odd number of vertices).[1] 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.[2]

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 it from being matched. This set of edges is called a trivial matching preclusion set.[2] 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.[3][4]

It is NP-complete to test whether the matching preclusion number of a given graph is below a given threshold.[5]

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

  1. ↑ Brigham, Robert C.; Harary, Frank; Violin, Elizabeth C.; Yellen, Jay (2005), "Perfect-matching preclusion", Congressus Numerantium (Utilitas Mathematica Publishing, Inc.) 174: 185–192.
  2. 1 2 Cheng, Eddie; Lipták, László (2007), "Matching preclusion for some interconnection networks", Networks 50 (2): 173–180, doi:10.1002/net.20187.
  3. ↑ Cheng, Eddie; Lesniak, Linda; Lipman, Marc J.; Lipták, László (2009), "Conditional matching preclusion sets", Information Sciences 179 (8): 1092–1101, doi:10.1016/j.ins.2008.10.029.
  4. ↑ Park, Jung-Heum; Son, Sang Hyuk (2009), "Conditional matching preclusion for hypercube-like interconnection networks", Theoretical Computer Science 410 (27-29): 2632–2640, doi:10.1016/j.tcs.2009.02.041.
  5. ↑ Dourado, Mitre Costa; Meierling, Dirk; Penso, Lucia D.; Rautenbach, Dieter; Protti, Fabio; de Almeida, Aline Ribeiro (2015), "Robust recoverable perfect matchings", Networks 66 (3): 210–213, doi:10.1002/net.21624.


This article is issued from Wikipedia - version of the Friday, November 13, 2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.