Relations between Metric Dimension and Domination Number of Graphs

Abstract

A set $W\subseteq V(G)$ is called a resolving set, if for each two distinct vertices $u,v\in V(G)$ there exists $w\in W$ such that $d(u,w)\ne d(v,w)$, where $d(x,y)$ is the distance between the vertices $x$ and $y$. The minimum cardinality of a resolving set for $G$ is called the metric dimension of $G$, and denoted by $\beta (G)$. In this paper, we prove that in a connected graph $G$ of order $n$, $\beta (G)\le n-\gamma (G)$, where $\gamma (G)$ is the domination number of $G$, and the equality holds if and only if $G$ is a complete graph or a complete bipartite graph $K_{s,t}$, $s,t\ge 2$. Then, we obtain new bounds for $\beta (G)$ in terms of minimum and maximum degree of $G$.

6 pages

References in corpus (1)

• On the Metric Dimension of Cartesian Products of Graphs

Cited by in corpus (1)

• Distance-$k$ locating-dominating sets in graphs