On the hardness of deciding the equality of the induced and the uniquely restricted matching number

摘要

If G(M) denotes the subgraph of a graph G induced by the set of vertices that are covered by some matching M in G, then M is an induced or a uniquely restricted matching if G(M) is 1-regular or if M is the unique perfect matching of G(M), respectively. Let v(s)(G) and v(ur)(G) denote the maximum cardinality of an induced and a uniquely restricted matching in G.Golumbic, Hirst, and Lewenstein (2001) [9] posed the problem to characterize the graphs G with v(ur)(G) = v(s)(G). We prove that the corresponding decision problem is NP-hard, which suggests that a good characterization is unlikely to be possible. (C) 2019 Elsevier B.V. All rights reserved.