On metric dimension of permutation graphs

The metric dimension $$\dim (G)$$ of a graph $$G$$ is the minimum number of vertices such that every vertex of $$G$$ is uniquely determined by its vector of distances to the set of chosen vertices. Let $$G_1$$ and $$G_2$$ be disjoint copies of a graph $$G$$ , and let $$\sigma : V(G_1) \rightarrow V(G_2)$$ be a permutation. Then, a permutation graph $$G_{\sigma }=(V, E)$$ has the vertex set $$V=V(G_1) \cup V(G_2)$$ and the edge set $$E=E(G_1) \cup E(G_2) \cup \{uv \mid v=\sigma (u)\}$$ . We show that $$2 \le \dim (G_{\sigma }) \le n-1$$ for any connected graph $$G$$ of order $$n$$ at least $$3$$ . We give examples showing that neither is there a function $$f$$ such that $$\dim (G) \dim (G_{\sigma })$$ for all pairs $$(G, \sigma )$$ . Further, we characterize permutation graphs $$G_{\sigma }$$ satisfying $$\dim (G_{\sigma })=n-1$$ when $$G$$ is a complete $$k$$ -partite graph, a cycle, or a path on $$n$$ vertices.