A Comparison Between the Zero Forcing Number and the Strong Metric Dimension of Graphs
- Additional Document Info
- View All
© Springer International Publishing Switzerland 2014. 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. The strong metric dimension, sdim(G), of a graph G is the minimum among cardinalities of all strong resolving sets: W ⊆ V (G) is a strong resolving set of G if for any u, v ∈ V (G), there exists an x ∈ W such that either u lies on an x-v geodesic or v lies on an x-u geodesic. In this paper, we prove that Z(G) ≤ sdim(G)+3r(G) for a connected graph G, where r(G) is the cycle rank of G. Further, we prove the sharp bound Z(G) ≤ sdim(G) when G is a tree or a unicyclic graph, and we characterize trees T attaining Z(T) = sdim(T). It is easy to see that sdim(T + e) - sdim(T) can be arbitrarily large for a tree T; we prove that sdim(T + e) ≥ sdim(T) - 2 and show that the bound is sharp.
COMBINATORIAL OPTIMIZATION AND APPLICATIONS (COCOA 2014)
author list (cited authors)
complete list of authors
Kang, Cong X||Yi, Eunjeong