Matching preclusion

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]

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. ^ a b 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 .
Stub icon This combinatorics-related article is a stub. You can help Wikipedia by expanding it.