On metric dimension of cube of trees

Abstract

Let $G=(V,E)$ be a connected graph and $d_G(u,v)$ be the shortest distance between the vertices $u$ and $v$ in $G$. A set $S=\{s_1,s_2,\cdots ,s_n\}\subset V(G)$ is said to be a {\em resolving set} if for all distinct vertices $u,v$ of $G$, there exist an element $s\in S$ such that $d(s,u)\ne d(s,v)$. The minimum cardinality of a resolving set for a graph $G$ is called the {\em metric dimension} of $G$ and it is denoted by $\beta (G)$. A resolving set having $\beta (G)$ number of vertices is named as {\em metric basis} of $G$. The metric dimension problem is to find a metric basis in a graph $G$, and it has several real-life applications in network theory, telecommunication, image processing, pattern recognition, and many other fields. In this article, we consider {\em cube of trees} $T^3=(V,E)$, where any two vertices $u,v$ are adjacent if and only if the distance between them is less than equal to three in $T$. We establish the necessary and sufficient conditions of a vertex subset of $V$ to become a resolving set for $T^3$. This helps determine the tight bounds (upper and lower) for the metric dimension of $T^3$. Then, for certain well-known cubes of trees, such as caterpillars, lobsters, spiders, and $d$-regular trees, we establish the boundaries of the metric dimension. Further, we characterize some restricted families of cube of trees satisfying $\beta (T^3)=\beta (T)$. We provide a construction showing the existence of a cube of tree attaining every positive integer value as their metric dimension.