On Metric Dimension of Graphs and ‘Their Complements

Abstract

The metric dimension of a graph $G$, denoted by $\text{dim}(G)$, is the minimum number of vertices such that all vertices are uniquely determined by their distances to the chosen vertices. For a graph $G$ and its complement $\overline{G}$, each of order $n\ge 4$ and connected, we show that

$$2\le \text{dim}(G)+\text{dim}(\overline{G})\le 2(n-3).$$

It is readily seen that $\text{dim}(G)+\text{dim}(\overline{G})=2$ if and only if $n=4$. We characterize graphs satisfying

$$\text{dim}(G)+\text{dim}(\overline{G})=2(n-3)$$

when $G$ is a tree or a unicyclic graph.