The metric dimension of the lexicographic product of graphs

S. W. Saputro, R. Simanjuntak, S. Uttunggadewa, H. Assiyatun, E. T. Baskoro, A. N.M. Salman, M. Bača

Producción científica: Contribución a una revistaArtículorevisión exhaustiva

54 Citas (Scopus)

Resumen

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.

Idioma originalInglés
Páginas (desde-hasta)1045-1051
Número de páginas7
PublicaciónDiscrete Mathematics
Volumen313
N.º9
DOI
EstadoPublicada - 6 may. 2013
Publicado de forma externa

Huella

Profundice en los temas de investigación de 'The metric dimension of the lexicographic product of graphs'. En conjunto forman una huella única.

Citar esto