Algorithmic aspect of \(k\)-tuple domination in graphs. (Q1860929)

A dominating set of a graph \(G=(V,E)\) is defined as a set of vertices \(D\) such that each vertex from \(V\) is adjacent to to some vertex from \(D\) or it belongs to \(D\). One possible generalization of a dominating set is an \(M\)-dominating set. Let each vertex \(v\) be associated with a label \(M(v)=(t(v),k(v))\), where \(t(v)\) is one of the symbols in \(\{B,R\}\) and \(k(v)\) is a nonnegative integer. We say that a set of vertices \(D\) is \(M\)-dominating if it satisfies the following conditions for all vertices: (M1) If \(t(v)=R\), then \(v\in D.\) (M2) \(\left| N_{G}[v]\cap D\right| \) \(\geq k(v)\) where \(N_{G}[v]\) is the closed neighborhood of vertex \(v\). The authors present a linear-time algorithm to find a minimal \(M\)-dominating set in a tree with given labelling \(M\). In the case when \(t(v)=B\) and \(k(v)=2\) for all vertices in \(V\), the \(M\)-dominating set is called \(2\)-tuple dominating set or double dominating set. In a graph each vertex is dominated by at least two vertices from a \(2\)-tuple dominating set. In the case \( k(v)=1\) the \(M\)-dominating set is the usual dominating set.