Dynamical \(2\)-domination in Graphs

Abstract

In this paper, a domination-type parameter, called dynamical \(2\)-domination number, will be introduced. Let \(G = (V(G), E(G))\) be a graph. A subset \(D \subseteq V(G)\) is called a \(2\)-dominating set in \(G\) if every vertex in \(V(G) \setminus D\) is adjacent to at least two vertices in \(D\), and in this paper \(D\) is called a dynamical \(2\)-dominating set if there exists a sequence of sets \(D = V_0 \subseteq V_1 \subseteq V_2 \subseteq \cdots \subseteq V_k = V(G)\) such that, for each \(i\), \(V_{i-1}\) is a \(2\)-dominating set in \(\langle V_i \rangle\), the induced subgraph generated by \(V_i\). Also, for a given graph \(G\), the size of its dynamical \(2\)-dominating sets of minimum cardinality will be called the dynamical \(2\)-domination number of \(G\) and will be denoted by \(\bar{\gamma}_{2}(G)\). We study some basic properties of dynamical \(2\)-dominating sets and compute \(\bar{\gamma}_{2}(G)\) for some graph classes. Also, some results about \(\bar{\gamma}_{2}\) of a number of binary operations on graphs are proved. A characterization of graphs with extreme values of \(\bar{\gamma}_{2}\) is presented. Finally, we study this concept for trees and give an upper bound and a lower bound for the dynamical \(2\)-domination number of trees.