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

Abstract

Let $\Gamma$ be a simple connected undirected graph with vertex set $V(\Gamma )$ and edge set $E(\Gamma )$. The metric dimension of a graph $\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=\{w_1,w_2,...,w_k\}$ of vertices in a graph $\Gamma$ and a vertex $v$ of $\Gamma$, 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 $\Gamma$ have different metric representations then the ordered set $W$ is called a resolving set of $\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 (\Gamma )$ of minimal doubly resolving sets of $\Gamma$, and the strong metric dimension for jellyfish graph $JFG(n,m)$ and cocktail party graph $CP(k+1)$.

arXiv admin note: substantial text overlap with arXiv:1905.10525, arXiv:1908.07854