Graphs in which some and every maximum matching is uniquely restricted
Lúcia Draque Penso, Dieter Rautenbach, Uéverton S. Souza · Journal of Graph Theory · 2018
Abstract A matching M in a graph G is uniquely restricted if there is no matching in G that is distinct from M but covers the same vertices as M. Solving a problem posed by Golumbic, Hirst, and Lewenstein, we characterize the graphs in which some maximum matching is uniquely restricted. Solving a problem posed by Levit and Mandrescu, we characterize the graphs in which every maximum matching is uniquely restricted. Both our characterizations lead to efficient recognition algorithms for the corresponding graphs.