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 SV（G） is a strong resolving set of G if ...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 SV（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.展开更多
文摘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 SV（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.
