Revisiting \(k\)-tuple dominating sets with emphasis on small values of \(k\) (Q2147590)

Let \(k\) be a positive integer and \(G\) a graph. A vertex subset \(S\) of \(G\) is said to be a \(k\)-tuple dominating set if \(|N[v]\cap S|\geq k\) for each vertex \(v\) of \(G\). The \(k\)-tuple domination number \(\gamma_{\times k}(G)\) of \(G\) is the minimum cardinality of a \(k\)-tuple dominating set in \(G\). The \(k\)-tuple domination number \(\gamma_{\times k}(G)\) of \(G\) is the minimum cardinality of a \(k\)-tuple dominating set in \(G\). For the special case \(k=2\), the resulting set and the graph parameter are called commonly the double dominating set and the double domination number. A vertex partition of \(G\) is said to be a \(k\)-tuple domatic partition of \(G\) if each partite set is a \(k\)-tuple dominating set in \(G\). The \(k\)-tuple domatic number \(d_{\times k}(G)\) of \(G\) is the maximum cardinality taken over all \(k\)-tuple domatic partitions of \(G\). In particular, \(d_{\times 1}(G)\) is simply denoted by \(d(G)\). It is well known that \(d(G)\leq \delta(G)+1\) for any graph \(G\). Furthermore, \(G\) is called domatically full if \(d(G)\leq \delta(G)+1\). For any graph \(G\) of order \(n\) with degree sequence \(d_1\geq \cdots \geq d_n\), the double Slater number \(sl_{\times 2}(G)\) is the smallest integer \(t\) such that \(t+d_1+\cdots+d_{t-e}\geq 2n-p\) in which \(e\) and \(p\) are the number of end-vertices and penultimate vertices of \(G\), respectively. The main results of the paper are listed below: (1) \(\gamma_{\times 2}(G)\geq sl_{\times 2}(G)\) for any graph \(G\) without isolated vertices and the problem of deciding whether the equality holds for a given graph is NP-complete even when restricted to 4-partite graphs; (2) the problem of computing \(\gamma_{\times 2}(G)\) is NP-hard even for comparability graphs of diameter two; (3) Some results concerning these two parameters are given in this paper improving and generalizing some earlier results on double domination in graphs; (4) An upper bound on the \(k\)-tuple domatic number of graphs with the characterization of all graphs attaining the bound; (5) A constructive characterization of all domatically full graphs, solving an open problem in a paper by \textit{E. J. Cockayne} and \textit{S. T. Hedetniemi} [Networks 7, 247--261 (1977; Zbl 0384.05051)].