The metric dimension of comb product graph

Abstract

A set of vertices $W$ \textit{resolves} a graph $G$ if every vertex is uniquely determined by its coordinate of distance to the vertices in $W$. The minimum cardinality of a resolving set of $G$ is called the \textit{metric dimension} of $G$. In this paper, we consider a graph which is obtained by the comb product between two connected graphs. Let $o$ be a vertex of $H$. The \textit{comb product} between $G$ and $H$, denoted by $G{⊳}_{o}H$, is a graph obtained by taking one copy of $G$ and $|V(G)|$ copies of $H$ and identifying the $i$-th copy of $H$ at the vertex $o$ to the $i$-th vertex of $G$. We give an exact value of the metric dimension of $G{⊳}_{o}H$ where $H$ is not a path or $H$ is a path where the vertex $o$ is not a leaf. We also give the sharp general bounds of $\beta (G{⊳}_o{P}_n)$ for $n\ge 2$ where the vertex $o$ is a leaf of $P_n$.