Paired-dominating set

Paired-dominating set --- парно-доминирующее множество.

A paired-dominating set [math]\displaystyle{ S }[/math] with a matching [math]\displaystyle{ M }[/math] is a dominating set [math]\displaystyle{ S = \{v_{1}, v_{2}, \ldots, v_{2t-1}, v_{2t}\} }[/math] with an independent edge set [math]\displaystyle{ M = \{e_{1}, \ldots, e_{t}\} }[/math], where each edge [math]\displaystyle{ e_{i} }[/math] joins two elements of [math]\displaystyle{ S }[/math], that is, [math]\displaystyle{ M }[/math] is a perfect matching (not necessarily induced) in the subgraph [math]\displaystyle{ \langle S \rangle }[/math] induced by [math]\displaystyle{ S }[/math]. A set [math]\displaystyle{ S }[/math] is called a paired-dominating set if it dominates [math]\displaystyle{ V }[/math] and [math]\displaystyle{ \langle S \rangle }[/math] contains at least one perfect matching. The paired-domination number [math]\displaystyle{ \gamma_{p}(G) }[/math] is the minimum cardinality of a paired-dominating set [math]\displaystyle{ S }[/math] in [math]\displaystyle{ G }[/math].