On connected \(k\)-domination numbers of graphs. (Q1421532): Difference between revisions

A subset \(D\) of the vertex set \(V\) of a graph \(G\) is called a connected \(k\)-dominating set (for a positive integer \(k)\) in \(G\), if for each vertex \(x\in V-D\) there exists a vertex \(y\in D\) such that the distance between \(x\) and \(y\) in \(G\) is at most \(k\) and moreover the subgraph \(G[D]\) of \(G\) induced by \(D\) is conneced. The minimum number of vertices of a connected \(k\)-dominating set in \(G\) is the connected \(k\)-domination number \(\gamma_k^c(G)\) of \(G\) and the maximum number of classes of a partition of \(V\) into connected \(k\)-dominating sets is the connected \(k\)-domatic number \(d^c_k(G)\) of \(G\). The symbol \(\overline G\) denotes the complement of \(G\). The main result of the paper states that if \(k\geq 2\) and both \(G\) and \(\overline G\) are connected, then \(\gamma_k^c(G)\leq(2k+1)d_k^c(G)\).