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

作者：Eroh Linda; Kang Cong X; Yi Eunjeong^*

来源：Acta Mathematica Sinica-English Series, 2017, 33(6): 731-747.

DOI：10.1007/s10114-017-4699-4

• Distance
• resolving set
• metric dimension
• zero forcing set
• zero forcing number
• tree
• unicyclic graph
• cycle rank

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 is an element of E (T) over bar.

• 出版日期2017-6