A Comparison between the Metric Dimension and Zero Forcing Number of Trees and Unicyclic Graphs Academic Article uri icon

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).

published proceedings

  • ACTA MATHEMATICA SINICA-ENGLISH SERIES

altmetric score

  • 0.25

author list (cited authors)

  • Eroh, L., Kang, C. X., & Yi, E.

citation count

  • 16

complete list of authors

  • Eroh, Linda||Kang, Cong X||Yi, Eunjeong

publication date

  • June 2017