Regresar

The metric dimension of the lexicographic product of graphs

Abstract:

A set of vertices W resolves a graph G if every vertex is uniquely determined by its coordinate of distances to the vertices in W. The minimum cardinality of a resolving set of G is called the metric dimension of G. In this paper, we consider a graph which is obtained by the lexicographic product between two graphs. The lexicographic product of graphs G and H, which is denoted by G o H, is the graph with vertex set V (G) × V (H) = {(a, v) |a ∈ V (G), v ∈ V (H)}, where (a, v) is adjacent to (b, ω) whenever ab ∈ E (G), or a = b and vω ∈ E (H). We give the general bounds of the metric dimension of a lexicographic product of any connected graph G and an arbitrary graph H. We also show that the bounds are sharp. © 2013 Elsevier B.V. All rights reserved.