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

preprint2012arXivOpen access

Abstract

A set of vertices WW {\em resolves} a graph GG if every vertex of GG is uniquely determined by its vector of distances to the vertices in WW. The {\em metric dimension} for GG, denoted by dim⁡(G)\dim(G), is the minimum cardinality of a resolving set of GG. In order to study the metric dimension for the hierarchical product G2u2⊓G1u1G_2^{u_2}\sqcap G_1^{u_1} of two rooted graphs G2u2G_2^{u_2} and G1u1G_1^{u_1}, we first introduce a new parameter, the {\em rooted metric dimension} $\rdim(G_1^{u_1})$ for a rooted graph G1u1G_1^{u_1}. If G1G_1 is not a path with an end-vertex u1u_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(G2)∣|V(G_2)| is the order of G2G_2. If G1G_1 is a path with an end-vertex u1u_1, we obtain some tight inequalities for dim⁡(G2u2⊓G1u1)\dim(G_2^{u_2}\sqcap G_1^{u_1}). Finally, we show that similar results hold for the fractional metric dimension.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.