On Dominating Sets and Independent Sets of Graphs (Q4946835)

Let \(V=\{1, 2, \dots{}, n\}\) be the vertex-set of an undirected simple graph, where vertex \(i\) has degree \(d_i\), and where \(k_i\) is an integer such that \(1\leq i\leq n\) \((i=1,2,\dots{},n)\); denote the vector \((k_1,k_2,\dots{},k_n)\) by \(\mathbf k\), and the maximum degree, \(\max\{d_i:1\leq i\leq n\}\) by \(\Delta\). A \(\mathbf k\)-dominating set \(D_{\mathbf k}\) is a set of vertices with the property that every vertex \(i\in V-D_{\mathbf k}\) has at least \(k_i\) neighbours in \(D_{\mathbf k}\). In Theorem 2.1 the authors determine the cardinality of the smallest \(\mathbf k\)-dominating set \(D_{\mathbf k}\); this cardinality is denoted by \(\gamma_{\mathbf k}(G)\), and is called the \(\mathbf k\)-domination number. In Theorem 2.4 they present an \(O(\Delta^22^\Delta n)\)-algorithm that constructs a smallest \(\mathbf k\)-dominating set. From the authors' abstract: Our approach yields an improvement of an upper bound for the domination number found by \textit{N. Alon} and \textit{J. H. Spencer} [The probabilistic method. With an appendix on open problems by Paul Erdős (Wiley-Interscience Series in Discrete Mathematics and Optimization. New York: John Wiley \& Sons) (1992; Zbl 0767.05001)]. Referring to the paper [\textit{Y. Caro} and \textit{Zs. Tuza}, Improved lower bounds on \(k\)-independence, J. Graph Theory 15, No. 1, 99-107 (1991; Zbl 0753.68079)], the authors observe, in closing, that unfortunately, we do not know appropriate values \dots{} for this algorithm to yield an independent set whose cardinality satisfies the Caro-Wei inequality.