The extended dominating sets in graphs

Planar graphs; geometric and topological aspects of graph theory (05C10) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Review text

Let \(G = (V (G), E(G))\) be a graph and let \(k\) be an integer. A vertex subset \(S\subseteq V (G)\) is called a \(k\)-extended dominating set if every vertex \(u\) of \(G\) satisfies one of the following conditions: the distance between \(u\) and \(S\) is at most one or there are at least \(k\) different vertices \(s_1, s_2, \dots, s_k \in S\) such that the distance between \(u\) and \(s_i\; (i \in [k])\) is two. The \(k\)-extended domination number \(\gamma_e^k(G)\) of \(G\) is the minimum size over all \(k\)-extended dominating sets in \(G\). In this paper, the authors study this parameter.\N\NIn [Quaest. Math. 37, No. 4, 547--561 (2014; Zbl 1404.05150)], \textit{W. Goddard} et al. introduced the concept of \(b\)-disjunctive domination number as follows: A set \(S \subseteq V (G)\) is said to be a \(b\)-disjunctive dominating set (\(b\)DDS) of \(G\), if every vertex \(v\) not in \(S\) is either adjacent to \(S\) or there are at least \(b\) vertices of \(S\) within distance two of \(v\) (or both). The \(b\)-disjunctive domination number, \(\gamma_b^d(G)\), is the minimum cardinality of a \(b\)-disjunctive dominating set.\N\NIt seems that these definitions are the same. This paper has some overlap with previous papers. For instance, Theorem 2.1 and 2.2 can be found in the paper mentioned above. However, the following good bound for planar graphs with diameter three is presented.\N\NTheorem. Let \(G\) be a planar graph with diameter 3 and radius 2. Then \(\gamma_e^2(G) \le 3\).

Recommendations

Cites work

Cited in

(2)

This page was built for publication: The extended dominating sets in graphs

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