On the strong metric dimension of corona product graphs and join graphs

Let GG be a connected graph. A vertex ww strongly resolves a pair uu, vv of vertices of GG if there exists some shortest u−wu−w path containing vv or some shortest v−wv−w path containing uu. A set WW of vertices is a strong resolving set for GG if every pair of vertices of GG is strongly resolved by some vertex of WW. The smallest cardinality of a strong resolving set for GG is called the strong metric dimension of GG. It is known that the problem of computing this invariant is NP-hard. It is therefore desirable to reduce the problem of computing the strong metric dimension of product graphs, to the problem of computing some parameter of the factor graphs. We show that the problem of finding the strong metric dimension of the corona product G⊙HG⊙H, of two graphs GG and HH, can be transformed to the problem of finding certain clique number of HH. As a consequence of the study we show that if HH has diameter two, then the strong metric dimension of G⊙HG⊙H is obtained from the strong metric dimension of HH and, if HH is not connected or its diameter is greater than two, then the strong metric dimension of G⊙HG⊙H is obtained from the strong metric dimension of K1⊙HK1⊙H, where K1K1 denotes the trivial graph. The strong metric dimension of join graphs is also studied.