R.-W. Hung, C.-H. Chiu, and C.-C. Yao (Taiwan)
graph algorithm; cograph; paired-domination; maximum matched-paired-domination; linear-time algorithm.
Let G = (V, E) be a graph without isolated vertices. A
matching in G is a set of independent edges in G. A perfect matching M in G is a matching such that every vertex
of G is incident to an edge of M. A set S ⊆ V is a paired
dominating set of G if every vertex in V − S is adjacent
to at least a vertex in S and if the subgraph G[S] induced
by S contains at least one perfect matching. The paired
domination problem is to nd a paired-dominating set of G
with minimum cardinality. In this paper, we will introduce
a generalization of the paired-domination problem, namely,
the maximum matched-paired-domination problem. We
then present a linear-time algorithm to solve it in cographs.