Metric Dimension, Minimal Doubly Resolving Sets, and the Strong Metric Dimension for Jellyfish Graph and Cocktail Party Graph
Jia‐Bao Liu, Ali Zafari, Hassan Zarei · Complexity · 2020
Let Γ be a simple connected undirected graph with vertex set VΓ and edge set EΓ . The metric dimension of a graph Γ 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=w1,w2,…,wk of vertices in a graph Γ and a vertex v of Γ , the metric representation of v with respect to W is the k -vector rvW=dv,w1,dv,w2,…,dv,wk . If every pair of distinct vertices of Γ have different metric representations, then the ordered set W is called a resolving set of Γ . It is known that the problem of computing this invariant is NP-hard. In this paper, we consider the problem of determining the cardinality ψΓ of minimal doubly resolving sets of Γ and the strong metric dimension for the jellyfish graph JFGn,m and the cocktail party graph CPk+1 .