A Comparison between the Metric Dimension and Zero Forcing Number of Trees and Unicyclic Graphs
Academic Article
Overview
Research
Identity
Additional Document Info
Other
View All
Overview
abstract
2017, Institute of Mathematics, Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Chinese Mathematical Society and Springer-Verlag Berlin Heidelberg. The 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 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. We show that dim(T) Z(T) for a tree T, and that dim(G) 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 dim(T + e) dim(T) + 1 for e E(T).