On the metric dimension and fractional metric dimension for hierarchical product of graphs

Min Feng; Kaishun Wang

paper

On the metric dimension and fractional metric dimension for hierarchical product of graphs

arXiv:1211.1432

Abstract

A set of vertices $W$ {\em resolves} a graph $G$ if every vertex of $G$ is uniquely determined by its vector of distances to the vertices in $W$ . The {\em metric dimension} for $G$ , denoted by $dim (G)$ , is the minimum cardinality of a resolving set of $G$ . In order to study the metric dimension for the hierarchical product $G_{2}^{u_{2}} ⊓ G_{1}^{u_{1}}$ of two rooted graphs $G_{2}^{u_{2}}$ and $G_{1}^{u_{1}}$ , we first introduce a new parameter, the {\em rooted metric dimension} $\rdim(G_1^{u_1})$ for a rooted graph $G_{1}^{u_{1}}$ . If $G_{1}$ is not a path with an end-vertex $u_{1}$ , we show that $\dim(G_2^{u_2}\sqcap G_1^{u_1})=|V(G_2)|\cdot\rdim(G_1^{u_1})$, where $∣ V (G_{2}) ∣$ is the order of $G_{2}$ . If $G_{1}$ is a path with an end-vertex $u_{1}$ , we obtain some tight inequalities for $dim (G_{2}^{u_{2}} ⊓ G_{1}^{u_{1}})$ . Finally, we show that similar results hold for the fractional metric dimension.

11 pages