2011/03/17 by Jannesari, Mohsen, Omoomi, Behnaz · 1 citation
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1103.3336
For an ordered set W=\w1,w2,...,wk\ of vertices and a vertex v in a connected graph G, the ordered k-vector r(v|W):=(d(v,w1),d(v,w2),...,d(v,wk)) is called the (metric) representation of v with respect to W, where d(x,y) is the distance between the vertices x and y. The set W is called a resolving set for G if distinct vertices of G have distinct representations with respect to W. The minimum cardinality of a resolving set for G is its metric dimension. In this paper, we study the metric dimension of the lexicographic product of graphs G and 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] in terms of the order of G and the adjacency metric dimension of H.