Restricted domination in graphs

DOI10.1016/S0012-365X(01)00371-5MaRDI QIDQ1613539zbMATH OpenOpenAlexFDO

Authors Michael A. Henning

Publication date 29 August 2002

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0012-365x(01)00371-5

zbMATH Keywords

domination number

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Review text

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\).

Recommendations

Cited in

(21)

This page was built for publication: Restricted domination in graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1613539)