Geodesic
Closed Formulae for the Strong Metric Dimension of Lexicographic Product Graphs
Discussiones Mathematicae. Graph Theory, Tome 36 (2016) no. 4, pp. 1051-1064.

Voir la notice de l'article provenant de la source Library of Science

Given a connected graph G, a vertex w ∈ V (G) strongly resolves two vertices u, v ∈ V (G) if there exists some shortest u − w path containing v or some shortest v − w path containing u. A set S of vertices is a strong metric generator for G if every pair of vertices of G is strongly resolved by some vertex of S. The smallest cardinality of a strong metric generator for G is called the strong metric dimension of G. In this paper we obtain several relationships between the strong metric dimension of the lexicographic product of graphs and the strong metric dimension of its factor graphs.
Keywords: strong metric dimension, strong metric basis, strong metric generator, lexicographic product graphs 
@article{DMGT_2016_36_4_a20,
     author = {Kuziak, Dorota and Yero, Ismael G. and Rodr{\'\i}guez-Vel\'azquez, Juan A.},
     title = {Closed {Formulae} for the {Strong} {Metric} {Dimension} of {Lexicographic} {Product} {Graphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {1051--1064},
     publisher = {mathdoc},
     volume = {36},
     number = {4},
     year = {2016},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2016_36_4_a20/}
}
TY  - JOUR
AU  - Kuziak, Dorota
AU  - Yero, Ismael G.
AU  - Rodríguez-Velázquez, Juan A.
TI  - Closed Formulae for the Strong Metric Dimension of Lexicographic Product Graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2016
SP  - 1051
EP  - 1064
VL  - 36
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2016_36_4_a20/
LA  - en
ID  - DMGT_2016_36_4_a20
ER  - 
%0 Journal Article
%A Kuziak, Dorota
%A Yero, Ismael G.
%A Rodríguez-Velázquez, Juan A.
%T Closed Formulae for the Strong Metric Dimension of Lexicographic Product Graphs
%J Discussiones Mathematicae. Graph Theory
%D 2016
%P 1051-1064
%V 36
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2016_36_4_a20/
%G en
%F DMGT_2016_36_4_a20
Kuziak, Dorota; Yero, Ismael G.; Rodríguez-Velázquez, Juan A. Closed Formulae for the Strong Metric Dimension of Lexicographic Product Graphs. Discussiones Mathematicae. Graph Theory, Tome 36 (2016) no. 4, pp. 1051-1064. http://geodesic.mathdoc.fr/item/DMGT_2016_36_4_a20/

[1] D. Geller and S. Stahl, The chromatic number and other functions of the lexicographic product, J. Combin. Theory Ser. B 19 (1975) 87-95. doi: 10.1016/0095-8956(75)90076-3

[2] R. Hammack, W. Imrich and S. Klavžar, Handbook of Product Graphs, 2nd Ed. (CRC Press, Boca Raton, 2011).

[3] F. Harary and R.A. Melter, On the metric dimension of a graph, Ars Combin. 2 (1976) 191-195.

[4] J. Kratica, V. Kovačević-Vujčić, M. Čangalović and M. Stojanović, Minimal doubly resolving sets and the strong metric dimension of some convex polytopes, Appl. Math. Comput. 218 (2012) 9790-9801. doi: 10.1016/j.amc.2012.03.047

[5] J. Kratica, V. Kovačević-Vujčić and M. Čangalović, Computing strong metric dimension of some special classes of graphs by genetic algorithms, Yugosl. J. Oper. Res. 18 (2008) 143-151. doi: 10.2298/YJOR0802143K

[6] J. Kratica, V. Kovačević-Vujčić, M. Čangalović and N. Mladenović, Strong metric dimension: A survey, Yugosl. J. Oper. Res. 24 (2014) 187-198. doi: 10.2298/YJOR130520042K

[7] D. Kuziak, I.G. Yero and J.A. Rodríguez-Velázquez, On the strong metric dimension of corona product graphs and join graphs, Discrete Appl. Math. 161 (2013) 1022-1027. doi: 10.1016/j.dam.2012.10.009

[8] D. Kuziak, I.G. Yero and J.A. Rodríguez-Velázquez, Strong metric dimension of rooted product graphs, Int. J. Comput. Math. 93 (2016) 1265-1280. doi: 10.1080/00207160.2015.1061656

[9] D. Kuziak, I.G. Yero and J.A. Rodríguez-Velázquez, Erratum to “On the strong metric dimension of the strong products of graphs”, Open Math. 13 (2015) 209-210. doi: 10.1515/math-2015-0020

[10] D. Kuziak, I.G. Yero and J.A. Rodríguez-Velázquez, On the strong metric dimension of the strong products of graphs, Open Math. 13 (2015) 64-74. doi: 10.1515/math-2015-0007

[11] T.R.May and O.R. Oellermann, The strong dimension of distance-hereditary graphs, J. Combin. Math. Combin. Comput. 76 (2011) 59-73.

[12] N. Mladenović, J. Kratica, V. Kovačević-Vujčić and M. Čangalović, Variable neighborhood search for the strong metric dimension problem, Electron. Notes Discrete Math. 39 (2012) 51-57. doi: 10.1016/j.endm.2012.10.008

[13] O.R. Oellermann and J. Peters-Fransen, The strong metric dimension of graphs and digraphs, Discrete Appl. Math. 155 (2007) 356-364. doi: 10.1016/j.dam.2006.06.009

[14] J.A. Rodríguez-Velázquez, I.G. Yero, D. Kuziak and O.R. Oellermann, On the strong metric dimension of Cartesian and direct products of graphs, Discrete Math. 335 (2014) 8-19. doi: 10.1016/j.disc.2014.06.023

[15] A. Sebő and E. Tannier, On metric generators of graphs, Math. Oper. Res. 29 (2004) 383-393. doi: 10.1287/moor.1030.0070

[16] P.J. Slater, Leaves of trees, Congr. Numer. 14 (1975) 549-559.

[17] E. Yi, On strong metric dimension of graphs and their complements, Acta Math. Sin. (Engl. Ser.) 29 (2013) 1479-1492. doi: 10.1007/s10114-013-2365-z