Induced-Paired Domination in Graphs

For a graph \(G = (V, E)\), a set \(S \subseteq V\) is a dominating set if every vertex in \(V – S\) is adjacent to at least one vertex in \(S\). A dominating set \(S \subseteq V\) is a paired-dominating set if the induced subgraph \(\langle S\rangle\) has a perfect matching. We introduce a variant of paired-domination where an additional restriction is placed on the induced subgraph \(\langle S\rangle \). A paired-dominating set \(S\) is an induced-paired dominating set if the edges of the matching are the induced edges of \(\langle S\rangle\), that is, \(\langle S\rangle\) is a set of independent edges. The minimum cardinality of an induced-paired dominating set of \(G\) is the induced-paired domination number \(\gamma_{ip}(G)\). Every graph without isolates has a paired-dominating set, but not all these graphs have an induced-paired dominating set. We show that the decision problem associated with induced-paired domination is NP-complete even when restricted to bipartite graphs and give bounds on \(\gamma_{ip}(G)\). A characterization of those triples \((a, b, c)\) of positive integers \(a \leq b \leq c\) for which a graph has domination number \(a\), paired-domination number \(b\), and induced-paired domination \(c\) is given. In addition, we characterize the cycles and trees that have induced-paired dominating sets.