Restricted domination in graphs (Q1613539): Difference between revisions
From MaRDI portal
Removed claim: reviewed by (P1447): Item:Q590664 |
Changed an Item |
||
Property / reviewed by | |||
Property / reviewed by: William G. Brown / rank | |||
Normal rank |
Revision as of 23:35, 19 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Restricted domination in graphs |
scientific article |
Statements
Restricted domination in graphs (English)
0 references
29 August 2002
0 references
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\).
0 references
domination number
0 references