A Comparison Between the Zero Forcing Number and the Strong Metric Dimension of Graphs
Academic Article

 Overview

 Research

 Identity

 Additional Document Info

 View All

Overview
abstract

© 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 colorchange 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 xv geodesic or v lies on an xu 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.
published proceedings

COMBINATORIAL OPTIMIZATION AND APPLICATIONS (COCOA 2014)
author list (cited authors)
citation count
complete list of authors

Kang, Cong XYi, Eunjeong
publication date
publisher
published in
Research
keywords

Cycle Rank

Strong Metric Dimension

Tree

Unicyclic Graph

Zero Forcing Number
Identity
Digital Object Identifier (DOI)
Additional Document Info
start page
end page
volume