Menu
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 \geq 3 \), the strong metric dimension of \( G_\sigma \) satisfies \( 2 \leq sdim(G_\sigma) \leq 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}) \leq 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.