Bounds on the sum of domination number and metric dimension of graphs
Academic Article
Overview
Research
Identity
Additional Document Info
Other
View All
Overview
abstract
Let [Formula: see text] be a graph with vertex set [Formula: see text]. The domination number, [Formula: see text], of [Formula: see text] is the minimum cardinality of a set [Formula: see text] such that every vertex not in [Formula: see text] is adjacent to a vertex in [Formula: see text]. The metric dimension, [Formula: see text], of [Formula: see text] is the minimum cardinality of a set of vertices such that every vertex of [Formula: see text] is uniquely determined by its vector of distances to the chosen vertices. For a tree [Formula: see text] of order at least two, we show that [Formula: see text], where [Formula: see text] denotes the number of exterior major vertices of [Formula: see text]; further, we characterize trees [Formula: see text] achieving equality. For a connected graph [Formula: see text] of order [Formula: see text], Bagheri Gh. et al. proved that [Formula: see text] and equality holds if and only if [Formula: see text] for [Formula: see text] and [Formula: see text], where [Formula: see text] denotes the complete graph and [Formula: see text] denotes a complete bi-partite graph of order [Formula: see text]. We characterize graphs [Formula: see text] for which [Formula: see text] equals two and three, respectively. We also characterize graphs [Formula: see text] satisfying [Formula: see text] when [Formula: see text] is a tree, a unicyclic graph, or a complete multi-partite graph.
