The Metric Dimension of Lexicographic Product of Graphs

preprint2011arXivOpen access

Abstract

For an ordered set W={w1,w2,...,wk}W=\{w_1,w_2,...,w_k\} of vertices and a vertex vv in a connected graph GG, the ordered kk-vector r(v∣W):=(d(v,w1),d(v,w2),...,d(v,wk))r(v|W):=(d(v,w_1),d(v,w_2),...,d(v,w_k)) is called the (metric) representation of vv with respect to WW, where d(x,y)d(x,y) is the distance between the vertices xx and yy. The set WW is called a resolving set for GG if distinct vertices of GG have distinct representations with respect to WW. The minimum cardinality of a resolving set for GG is its metric dimension. In this paper, we study the metric dimension of the lexicographic product of graphs GG and HH, G[H]G[H]. First, we introduce a new parameter which is called adjacency metric dimension of a graph. Then, we obtain the metric dimension of G[H]G[H] in terms of the order of GG and the adjacency metric dimension of HH.

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.