TY - JOUR

T1 - The metric dimension of the lexicographic product of graphs

AU - Saputro, S. W.

AU - Simanjuntak, R.

AU - Uttunggadewa, S.

AU - Assiyatun, H.

AU - Baskoro, E. T.

AU - Salman, A. N.M.

AU - Bača, M.

PY - 2013/5/6

Y1 - 2013/5/6

N2 - 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.

AB - 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.

KW - Basis

KW - Lexicographic product

KW - Metric dimension

KW - Resolving set

UR - http://www.scopus.com/inward/record.url?scp=84893696899&partnerID=8YFLogxK

U2 - 10.1016/j.disc.2013.01.021

DO - 10.1016/j.disc.2013.01.021

M3 - Artículo

AN - SCOPUS:84893696899

SN - 0012-365X

VL - 313

SP - 1045

EP - 1051

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 9

ER -