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

Abstract

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)\setminus 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\le \dim (T+e)\le \dim (T)+1$ for $e\in E(\overline{T})$.

15 pages, 14 figures

References in corpus (2)

• Propagation time for zero forcing on a graph
• On Zero Forcing Number of Graphs and Their Complements

Cited by in corpus (1)

• The connected metric dimension at a vertex of a graph