On the Strong Metric Dimension of Permutation Graphs

Abstract

A vertex $x$ in a graph $G$ strongly resolves a pair of vertices $v$ and $w$ if there exists a shortest path from $x$ to $w$ that contains $v$, or a shortest path from $x$ to $v$ that contains $w$ in $G$. A set of vertices $S\subseteq V(G)$ is a strong resolving set of $G$ if every pair of distinct vertices in $G$ is strongly resolved by some vertex in $S$. The strong metric dimension $sdim(G)$ of a graph $G$ is the minimum cardinality of a strong resolving set of $G$.

Given two disjoint copies of a graph $G$, denoted $G_1$ and $G_2$, and a permutation $\sigma :V(G_1)\to V(G_2)$, the permutation graph $G_{\sigma }=(V,E)$ is defined with vertex set $V=V(G_1)\cup V(G_2)$ and edge set $E=E(G_1)\cup E(G_2)\cup \{uv\mid v=\sigma (u)\}$.

We show that for a connected graph $G$ of order $n\ge 3$, the strong metric dimension of $G_{\sigma }$ satisfies $2\le sdim(G_{\sigma })\le 2n–2$. We also provide an example demonstrating that there is no function $f$ such that $f(sdim(G))>sdim(G_{\sigma })$ for all pairs $(G,\sigma )$. Additionally, we prove that $sdim(G_{{\sigma }_o})\le 2sdim(G)$ when ${\sigma }_o$ is the identity permutation.

Further, we characterize permutation graphs $G_{\sigma }$ that satisfy $sdim(G_{\sigma })=2n–2$ or $2n–3$ when $G$ is a complete $k$-partite graph, a cycle, or a path on $n$ vertices.