A Comparison Between the Zero Forcing Number and the Strong Metric Dimension of Graphs
Additional Document Info
Springer International Publishing Switzerland 2014. The zero forcing number, Z(G), of a graph G is the minimum cardinality of a set S of black vertices (whereas vertices in V (G) - S are colored white) such that V (G) is turned black after finitely many applications of the color-change rule: a white vertex is converted black if it is the only white neighbor of a black vertex. The strong metric dimension, sdim(G), of a graph G is the minimum among cardinalities of all strong resolving sets: W V (G) is a strong resolving set of G if for any u, v V (G), there exists an x W such that either u lies on an x-v geodesic or v lies on an x-u geodesic. In this paper, we prove that Z(G) sdim(G)+3r(G) for a connected graph G, where r(G) is the cycle rank of G. Further, we prove the sharp bound Z(G) sdim(G) when G is a tree or a unicyclic graph, and we characterize trees T attaining Z(T) = sdim(T). It is easy to see that sdim(T + e) - sdim(T) can be arbitrarily large for a tree T; we prove that sdim(T + e) sdim(T) - 2 and show that the bound is sharp.