On strong metric dimension of graphs and their complements
Academic Article
Overview
Research
Identity
Additional Document Info
Other
View All
Overview
abstract
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 , each of order n 4 and connected, we show that 2 sdim(G) + sdim() 2(n - 2). It is readily seen that sdim(G) + sdim() = 2 if and only if n = 4; we show that, when G is a tree or a unicyclic graph, sdim(G) + sdim() = 2(n - 2) if and only if n = 5 and G G C5, the cycle on five vertices. For connected graphs G and of order n 5, we show that 3 sdim(G) + sdim() 2(n - 3) if G is a tree; we also show that 4 sdim(G) + sdim() 2(n - 3) if G is a unicyclic graph of order n 6. Furthermore, we characterize graphs G satisfying sdim(G) + sdim() = 2(n - 3) when G is a tree or a unicyclic graph. 2013 Institute of Mathematics, Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Chinese Mathematical Society and Springer-Verlag Berlin Heidelberg.
