On the 2-metric resolvability of graphs

Abstract

Let $G=(V(G),E(G))$ be a graph. An ordered set of vertices $\Re=\{v_1,v_2,\ldots,v_l\}$ is a $2-$resolving set for $G$ if for any distinct vertices $s,w \in V(G)$, the representation of vertices $r(s|\Re)=(d_G(s,v_1),\ldots,d_G(s,v_l))$ and $r(w|\Re)=(d_G(w,v_1),\ldots, d_G(w,v_l))$ differs in at least $2$ positions. A $2-$resolving set of minimum cardinality is called a $2-$metric basis of $G$ and its cardinality is called the $2-$metric dimension (fault-tolerant metric dimension). In this article, the exact value of the $2-$metric dimension of the family circulant graph $C_n(1,2)$ is computed and thereby disproving the conjecture given by H. Raza et al., [Mathematics. 2019, 7(1), 78]. The $2-$metric dimension of the family generalized prism graph $P_m\times C_n$ and the Möbius ladder graph $M_n$ is computed. Furthermore, we improved the result given by M. Ali et al., [Ars Combinatoria 2012, 105, 403-410].

Keywords

• <i>k</i>−metric dimension
• circulant graph
• the generalized prism graph
• möbius ladder