Paper detail

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

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 = \{w_1, w_2, ..., w_k\}$ of vertices in a graph $Γ$ and a vertex $v$ of $Γ$, the metric representation of $v$ with respect to $W$ is the $k$-vector $r(v | W) = (d(v, w_1), d(v, w_2), ..., d(v, w_k ))$. 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 jellyfish graph $JFG(n, m)$ and cocktail party graph $CP(k+1)$.