Restricted domination in graphs (Q1613539): Difference between revisions

Let \(G=(V,E)\) be a graph in which \(|V|=n\), \(|E|=q\). For any \(U\subseteq V\), the restricted domination number \(r(G,U,\gamma)\) is the minimum cardinality of a set \(S\) such that \(U\subseteq S\subseteq V\) where every vertex not in \(S\) is adjacent to a vertex in \(S\); the \(k\)-restricted domination number \(r_k(G,\gamma)\) [\textit{L. A. Sanchis}, J. Graph Theory 25, 139-152 (1997; Zbl 0876.05047)] is \(\max_{U}\{ r(G,U,\gamma):U\subseteq V\) and \(|U|=k\}\). The main result is Theorem 10. For \(1\leq k\leq n\), if \(G\) is a connected graph of order \(n\) with minimum degree \(\delta(G)\geq 2\), then \(r_k(G,\gamma)\leq\frac{2n+3k}5\). The bound is sharp in the sense that, given any integers \(k\in\{2,3\}\) and \(\ell\geq 2\), or \(k\geq 3\) and \(\ell\geq 0\), there exists a family \({\mathcal G}_{k,\ell}\) of graphs \(G_{k,\ell}\), each of order \(n=k+5\ell\), with \(\delta(G_{k,\ell})\geq 2\) satisfying \(r_k(G_{k,\ell},\gamma)=\frac{2n+3k}5\).