Maximum Cardinality Simple 2-matchings in Subcubic Graphs
David Hartvigsen, Yanjun Li · SIAM Journal on Optimization · 2011
A simple 2-matching in a graph is a subset of edges [Formula: see text] such that every node is incident with at most two edges in [Formula: see text]. A simple 2-matching is called [Formula: see text]-restricted ([Formula: see text]) if it contains no cycles of length [Formula: see text] or less. We begin by considering the problem of finding maximum cardinality simple 2-matchings in subcubic graphs (i.e., graphs whose nodes have degree at most 3). For this problem we present a min-max theorem, a simple polynomial-time algorithm, and some other results. Then, by generalizing an approach due to Vornberger, we show the following for subcubic graphs: the maximum cardinality [Formula: see text]- and [Formula: see text]-restricted simple 2-matching problems are polynomial-time solvable; there exist min-max theorems for these problems; and, for [Formula: see text], the maximum cardinality [Formula: see text]-restricted simple 2-matching problems are NP-hard.