MATEMATIČKI VESNIK
МАТЕМАТИЧКИ ВЕСНИК



MATEMATIČKI VESNIK
The metric dimension of comb product graph
S.W. Saputro, N. Mardiana, 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$.

Creative Commons License

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

MSC: 05C12, 05C76

Pages:  248--258     

Volume  69 ,  Issue  4 ,  2017