Metric dimension, minimal doubly resolving sets, and the strong metric dimension for jellyfish graph and cocktail party graph (Q2188178)

Summary: Let \(\operatorname{\Gamma}\) be a simple connected undirected graph with vertex set \(V\left( \operatorname{\Gamma}\right)\) and edge set \(E\left( \operatorname{\Gamma}\right)\). The metric dimension of a graph \(\operatorname{\Gamma}\) is the least number of vertices in a set with the property that the list of distances from any vertex to those in the set uniquely identifies that vertex. For an ordered subset \(W=\left\{ w_1 , w_2 , \ldots , w_k\right\}\) of vertices in a graph \(\operatorname{\Gamma}\) and a vertex \(v\) of \(\operatorname{\Gamma} \), the metric representation of \(v\) with respect to \(W\) is the \(k\)-vector \(r\left( \left. v\right| W\right)=\left( d \left( v , w_1\right) , d \left( v , w_2\right) , \ldots , d \left( v , w_k\right)\right)\). If every pair of distinct vertices of \(\operatorname{\Gamma}\) have different metric representations, then the ordered set \(W\) is called a resolving set of \(\operatorname{\Gamma} \). It is known that the problem of computing this invariant is NP-hard. In this paper, we consider the problem of determining the cardinality \(\psi\left( \operatorname{\Gamma}\right)\) of minimal doubly resolving sets of \(\operatorname{\Gamma}\) and the strong metric dimension for the jellyfish graph \(\text{JFG}\left( n , m\right)\) and the cocktail party graph \(\text{CP}\left( k + 1\right)\).