On the equality of the induced matching number and the uniquely restricted matching number for subcubic graphs

Publication date 27 December 2019

Abstract: For a matching

M

in a graph

G

, let

G (M)

be the subgraph of

G

induced by the vertices of

G

that are incident with an edge in

M

. The matching

M

is induced, if

G (M)

is

1

-regular, and

M

is uniquely restricted, if

M

is the unique perfect matching of

G (M)

. The induced matching number

u_{s} (G)

of

G

is the largest size of an induced matching in

G

, and the uniquely restricted matching number

u_{u r} (G)

of

G

is the largest size of a uniquely restricted matching in

G

. Golumbic, Hirst, and Lewenstein (Uniquely restricted matchings, Algorithmica 31 (2001) 139-154) posed the problem to characterize the graphs

G

with

u_{s} (G) = u_{u r} (G)

. We give a complete characterization of the

2

-connected subcubic graphs

G

of sufficiently large order with

u_{s} (G) = u_{u r} (G)

. As a consequence, we are able to show that the subcubic graphs

G

with

u_{s} (G) = u_{u r} (G)

can be recognized in polynomial time.

Recommendations

Cites work

Cited in

(7)

This page was built for publication: On the equality of the induced matching number and the uniquely restricted matching number for subcubic graphs