A Comparison Between the Zero Forcing Number and the Strong Metric Dimension of Graphs
Academic Article

Overview

Research

Identity

Additional Document Info

View All

Overview

abstract

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.