2019/08/08 by Shahbaznejad, Najibeh, Pelayo, Ignacio M., Kazemi, Adel P.
#05C35 #05C69 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1908.03039
Let S be a set of vertices of a graph G. Let cl(S) be the set of vertices built from S, by iteratively applying the following propagation rule: if a vertex and all but exactly one of its neighbors are in cl(S), then the remaining neighbor is also in cl(S). A set S is called a zero forcing set of G if cl(S)=V(G). The zero forcing number Z(G) of G is the minimum cardinality of a zero forcing set. Let cl(N[S]) be the set of vertices built from the closed neighborhood N[S] of S, by iteratively applying the previous propagation rule. A set S is called a power dominating set of G if cl(N[S])=V(G). The power domination number \gp(G) of G is the minimum cardinality of a power dominating set. In this paper, we characterize the set of all graphs G for which Z(G)=2. On the other hand, we present a variety of sufficient and/or necessary conditions for a graph G to satisfy 1 ≤ \gp(G) ≤ 2.