On strong metric dimension of graphs and their complements.

A vertex x in a graph G strongly resolves a pair of vertices v,w if there exists a shortest x − w path containing v or a shortest x − v path containing w in G. A set of vertices S ⊆ V ( G) is a strong resolving set of G if every pair of distinct vertices of G is strongly resolved by some vertex in S. The strong metric dimension of G, denoted by sdim( G), is the minimum cardinality over all strong resolving sets of G. For a connected graph G of order n ≥ 2, we characterize G such that sdim( G) equals 1, n − 1, or n − 2, respectively. We give a Nordhaus-Gaddum-type result for the strong metric dimension of a graph and its complement: for a graph G and its complement $$\bar G$$, each of order n ≥ 4 and connected, we show that $$2 \leqslant sdim\left( G \right) + sdim\left( {\bar G} \right) \leqslant 2\left( {n - 2} \right)$$. It is readily seen that $$sdim\left( G \right) + sdim\left( {\bar G} \right) = 2$$ if and only if n = 4; we show that, when G is a tree or a unicyclic graph, $$sdim\left( G \right) + sdim\left( {\bar G} \right) = 2\left( {n - 2} \right)$$ if and only if n = 5 and $$G \cong \bar G \cong C_5$$, the cycle on five vertices. For connected graphs G and $$\bar G$$ of order n ≥ 5, we show that $$3 \leqslant sdim\left( G \right) + sdim\left( {\bar G} \right) \leqslant 2\left( {n - 3} \right)$$ if G is a tree; we also show that $$4 \leqslant sdim\left( G \right) + sdim\left( {\bar G} \right) \leqslant 2\left( {n - 3} \right)$$ if G is a unicyclic graph of order n ≥ 6. Furthermore, we characterize graphs G satisfying $$sdim\left( G \right) + sdim\left( {\bar G} \right) = 2\left( {n - 3} \right)$$ when G is a tree or a unicyclic graph. [ABSTRACT FROM AUTHOR]