On the strong metric dimension of composed graphs

12/08/2022

∙

by   Marcel Wagner, et al.

∙

0

∙

share

Two vertices u and v of an undirected graph G are strongly resolved by a vertex w if there is a shortest path between w and u containing v or a shortest path between w and v containing u. A vertex set R is a strong resolving set for G if for each pair of vertices there is a vertex in R that strongly resolves them. The strong metric dimension of G is the size of a minimum strong resolving set for G. We show that a minimum strong resolving set for an undirected graph G can be computed efficiently if and only if a minimum strong resolving set for each biconnected component of G can be computed efficiently.