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 G., each of order n . 4 and connected, we show that 2.sdim(G)+sdim(G.).2(n.2). It is readily seen that sdim(G)+sdim(G.)=2 if and only if n = 4; we show that, when G is a tree or a unicyclic graph, sdim(G)+sdim(G.)=2(n.2) if and only if n = 5 and G.G..C5, the cycle on five vertices. For connected graphs G and G. of order n . 5, we show that 3.sdim(G)+sdim(G.).2(n.3) if G is a tree; we also show that 4.sdim(G)+sdim(G.).2(n.3) if G is a unicyclic graph of order n . 6. Furthermore, we characterize graphs G satisfying sdim(G)+sdim(G.)=2(n.3) when G is a tree or a unicyclic graph.