The metric dimension of comb product graph

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

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\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$.

Keywords: Basis; comb product; metric dimension; resolving set.

Classification (MSC2000): 05C12; 05C76

Full text of the article: (for faster download, first choose a mirror)

• PDF file (376 kilobytes)