The metric dimension of a graph is defined as the smallest size of a set of vertices that uniquely determines the position of every vertex in the graph based on its distances to the vertices in that set. The lexicographic product of graphs $G$ and $H$, denoted by $G \circ H$, is a graph with the vertex set $V(G) \times V(H)$, where two vertices $(a,v)$ and $(b,w)$ are adjacent if $ab \in E(G)$ or $a=b$ and $vw \in E(H)$. The bounds of the metric dimension of the lexicographic product $G \circ H$, where $G$ is connected, depend on the order of the graph $G$, the number of components of the graph $H$, the metric dimensions of the components of the graph $H$, and the metric dimensions of joint graphs $H_i + K_1$, where $H_i$ are components of graph $H$. The adjacency dimension of a graph is defined as the smallest size of a set of vertices that uniquely determines the position of every vertex in the graph based on its adjacency to the vertices in that set. Vertices $u$ and $v$ are twins if $N(u) \setminus \{v\} = N(v) \setminus \{u\}$, where $N(u)$ denotes the neighborhood of vertex $u$. This is an equivalence relation, and its equivalence classes can be of three different types. If the properties of the neighborhood bases of the graph $H$ and the number of equivalence classes of different types with respect to the twin relation in the graph $G$ are known, we can give explicit formula for the metric dimension of the graph $G \circ H$.
|
