On the minimum doubly resolving set problem in line graphs

Given a connected graph $G$ with at least three vertices, let $d_G(u,v)$ denote the distance between vertices $u,v\in V(G)$. A subset $S\subseteq V$ is called a doubly resolving set (DRS) of $G$ if for any two distinct vertices $u,v\in V(G)$, there exists a pair $\{x,y\}\subseteq S$ such that $d_G(u,x)-d_G(u,y)\mathrm{\ne }{d}_G(v,x)-d_G(v,y)$. This paper studies the minimum cardinality of a DRS in the line graph of $G$, denoted by $\mathrm{\Psi }(L(G))$. First, we prove that computing $\mathrm{\Psi }(L(G))$ is NP-hard, even when $G$ is a bipartite graph. Second, we establish that $\lceil {\log }_2(1+\mathrm{\Delta }(G))\rceil \le \mathrm{\Psi }(L(G))\le \mathrm{\mid }V(G)\mathrm{\mid }-1$ holds for all $G$ with maximum degree $\mathrm{\Delta }(G)$, and show that both inequalities are tight. Finally, we determine the exact value of $\mathrm{\Psi }(L(G))$ provided $G$ is a tree.