The metric dimension of comb product graph


S. W. Saputro, N. Mardiana, I. A. Purwasih




A set of vertices $W$ extit{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 extit{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 extit{comb product} between $G$ and $H$, denoted by $G\rhd_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\rhd_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\rhd_o P_n)$ for $n\geq 2$ where the vertex $o$ is a leaf of $P_n$.