Graphs in which some and every maximum matching is uniquely restricted.

Abstract: A matching M in a graph G is uniquely restricted if there is no matching M ′ 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. [ABSTRACT FROM AUTHOR]