Strong metric dimension of rooted product graphs

Abstract

Let G be a connected graph. A vertex w strongly resolves two different vertices $u,v$ of G if there exists a shortest $u-w$ path, which contains the vertex v or a shortest $v-w$ path, which contains the vertex u. A set W of vertices is a strong metric generator for G if every pair of different vertices of G is strongly resolved by some vertex of W. The smallest cardinality of a strong metric generator for G is called the strong metric dimension of G. It is known that the problem of computing this invariant is NP-hard. According to that fact, in this paper we study the problem of computing exact values or sharp bounds for the strong metric dimension of the rooted product of graphs and express these in terms of invariants of the factor graphs.

Keywords:

• strong metric dimension
• rooted product graphs
• strong metric basis
• strong metric generator

2010 AMS Subject Classifications:

• 05C12
• 05C69
• 05C76

Disclosure statement

No potential conflict of interest was reported by the authors.

Notes

1. In fact, according to [21] the strong resolving graph $G_{\mathrm{SR}}^{\prime }$ of a graph G has vertex set $V\left(G_{\mathrm{SR}}^{\prime }\right)=V\left(G\right)$ and two vertices $u,v$ are adjacent in $G_{\mathrm{SR}}^{\prime }$ if and only if u and v are mutually maximally distant in G. So, the strong resolving graph defined here is a subgraph of the strong resolving graph defined in [21] and it can be obtained from the latter graph by deleting its isolated vertices.