On Distance Connected Domination Numbers of Graphs

Abstract

Let \(k\) be a positive integer and \(G = (V, E)\) be a connected graph of order \(n\). A set \(D \subseteq V\) is called a \(k\)-dominating set of \(G\) if each \(x \in V(G) – D\) is within distance \(k\) from some vertex of \(D\). A connected \(k\)-dominating set is a \(k\)-dominating set that induces a connected subgraph of \(G\). The connected \(k\)-domination number of \(G\), denoted by \(\gamma_k^c(G)\), is the minimum cardinality of a connected \(k\)-dominating set. Let \(\delta\) and \(\Delta\) denote the minimum and the maximum degree of \(G\), respectively. This paper establishes that \(\gamma_k^c(G) \leq \max\{1, n – 2k – \Delta + 2\}\), and \(\gamma_k^c(G) \leq (1 + o_\delta(1))n \frac{ln[m(\delta+1)+2-t]}{m(\delta+1)+2-t}\), where \(m = \lceil \frac{k}{3} \rceil\), \(t = 3 \lceil \frac{k}{3} \rceil – k\), and \(o_\delta(1)\) denotes a function that tends to \(0\) as \(\delta \to \infty\). The later generalizes the result of Caro et al. in [Connected domination and spanning trees with many leaves. SIAM J. Discrete Math. 13 (2000), 202-211] for \(k = 1\).