Metric Dimension, Minimal Doubly Resolving Sets, and the Strong Metric Dimension for Jellyfish Graph and Cocktail Party Graph

Abstract EN

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.