A Comparison between the Metric Dimension and Zero Forcing Number of Trees and Unicyclic Graphs

The \emph{metric dimension} $\dim (G)$ of a graph $G$ is the minimum number of vertices such that every vertex of $G$ is uniquely determined by its vector of distances to the chosen vertices. The \emph{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)\text{\hspace{0.17em}⁣}\setminus \text{\hspace{0.17em}⁣}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. We show that $\dim (T)\le Z(T)$ for a tree $T$, and that $\dim (G)\le Z(G)+1$ if $G$ is a unicyclic graph, along the way, we characterize trees $T$ attaining $\dim (T)=Z(T)$. For a general graph $G$, we introduce the “cycle rank conjecture”. We conclude with a proof of $\dim(T)-2 \leq \dim(T+e) \le \dim(T)+1$for$e \in E(\overline{T})$.