Geodesic
Computing the Metric Dimension of a Graph from Primary Subgraphs
Discussiones Mathematicae. Graph Theory, Tome 37 (2017) no. 1, pp. 273-293.

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

Let G be a connected graph. Given an ordered set W = w1, . . ., wk ⊆ V (G) and a vertex u ∈ V (G), the representation of u with respect to W is the ordered k-tuple (d(u, w1), d(u, w2), . . ., d(u, wk)), where d(u, wi) denotes the distance between u and wi. The set W is a metric generator for G if every two different vertices of G have distinct representations. A minimum cardinality metric generator is called a metric basis of G and its cardinality is called the metric dimension of G. It is well known that the problem of finding the metric dimension of a graph is NP-hard. In this paper we obtain closed formulae for the metric dimension of graphs with cut vertices. The main results are applied to specific constructions including rooted product graphs, corona product graphs, block graphs and chains of graphs.
Keywords: metric dimension, metric basis, primary subgraphs, rooted product graphs, corona product graphs 
@article{DMGT_2017_37_1_a19,
     author = {Kuziak, Dorota and Rodr{\'\i}guez-Vel\'azquez, Juan A. and Yero, Ismael G.},
     title = {Computing the {Metric} {Dimension} of a {Graph} from {Primary} {Subgraphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {273--293},
     publisher = {mathdoc},
     volume = {37},
     number = {1},
     year = {2017},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2017_37_1_a19/}
}
TY  - JOUR
AU  - Kuziak, Dorota
AU  - Rodríguez-Velázquez, Juan A.
AU  - Yero, Ismael G.
TI  - Computing the Metric Dimension of a Graph from Primary Subgraphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2017
SP  - 273
EP  - 293
VL  - 37
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2017_37_1_a19/
LA  - en
ID  - DMGT_2017_37_1_a19
ER  - 
%0 Journal Article
%A Kuziak, Dorota
%A Rodríguez-Velázquez, Juan A.
%A Yero, Ismael G.
%T Computing the Metric Dimension of a Graph from Primary Subgraphs
%J Discussiones Mathematicae. Graph Theory
%D 2017
%P 273-293
%V 37
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2017_37_1_a19/
%G en
%F DMGT_2017_37_1_a19
Kuziak, Dorota; Rodríguez-Velázquez, Juan A.; Yero, Ismael G. Computing the Metric Dimension of a Graph from Primary Subgraphs. Discussiones Mathematicae. Graph Theory, Tome 37 (2017) no. 1, pp. 273-293. http://geodesic.mathdoc.fr/item/DMGT_2017_37_1_a19/

[1] L. Barriȩre, F. Comellas, C. Dalfó and M.A. Fiol, The hierarchical product of graphs, Discrete Appl. Math. 157 (2009) 36–48. doi:10.1016/j.dam.2008.04.018

[2] L.M. Blumenthal, Theory and Applications of Distance Geometry, Second Edition (Chelsea Publishing Co., New York, 1970).

[3] J. Cáceres, C. Hernando, M. Mora, I.M. Pelayo, M.L. Puertas, C. Seara and D.R. Wood, On the metric dimension of Cartesian product of graphs, SIAM J. Discrete Math. 21 (2007) 423–441. doi:10.1137/050641867

[4] G. Chartrand, L. Eroh, M.A. Johnson and O.R. Oellermann, Resolvability in graphs and the metric dimension of a graph, Discrete Appl. Math. 105 (2000) 99–113. doi:10.1016/S0166-218X(00)00198-0

[5] G. Chartrand, C. Poisson and P. Zhang, Resolvability and the upper dimension of graphs, Comput. Math. Appl. 39 (2000) 19–28. doi:10.1016/S0898-1221(00)00126-7

[6] E. Deutsch and S. Klavžar, Computing the Hosoya polynomials of graphs from primary subgraphs, MATCH Commun. Math. Comput. Chem. 70 (2013) 627–644.

[7] E. Deutsch and J.A. Rodríguez-Velázquez, The terminal Hosoya polynomial of some families of composite graphs, Int. J. Com. 2014 (2014) Art. ID 696507. doi:10.1155/2014/696507

[8] J. Díaz, O. Pottonen, M. Serna and E. Jan van Leeuwen, On the complexity of metric dimension, Lecture Notes in Comput. Sci. 7501 (2012) 419–430. doi:10.1007/978-3-642-33090-2_37

[9] D. Eppstein, Metric dimension parameterized by max leaf number, J. Graph Algorithms Appl. 19 (2015) 313–323. doi:10.7155/jgaa.00360

[10] M. Feng and K. Wang, On the metric dimension and fractional metric dimension of the hierarchical product of graphs, Appl. Anal. Discrete Math. 7 (2013) 302–313. doi:10.2298/AADM130521009F

[11] H. Fernau, P. Heggernes, P. van’t Hof, D. Meister and R. Saei, Computing the metric dimension for chain graphs, Inform. Process. Lett. 115 (2015) 671–676. doi:10.1016/j.ipl.2015.04.006

[12] H. Fernau and J.A. Rodríguez-Velázquez, On the ( adjacency ) metric dimension of corona and strong product graphs and their local variants: combinatorial and computational results, arXiv:1309.2275 [math.CO] (2013).

[13] H. Fernau and J.A. Rodríguez-Velázquez, Notions of metric dimension of corona products: Combinatorial and computational results, Lecture Notes in Comput. Sci. 8476 (2014) 153–166. doi:10.1007/978-3-319-06686-8_12

[14] R. Frucht and F. Harary, On the corona of two graphs, Aequationes Math. 4 (1970) 322–325. doi:10.1007/BF01844162

[15] M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness (W.H. Freeman & Co., New York NY, USA, 1979).

[16] C.D. Godsil and B.D. McKay, A new graph product and its spectrum, Bull. Aust. Math. Soc. 18 (1978) 21–28. doi:10.1017/S0004972700007760

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

[18] S. Hartung and A. Nichterlein, On the parameterized and approximation hardness of metric dimension, in: Proceedings of the IEEE Conference on Computational Complexity, Stanford, California, USA (2013) 266–276.

[19] H. Iswadi, E.T. Baskoro and R. Simanjuntak, On the metric dimension of corona product of graphs, Far East J. Math. Sci. 52 (2011) 155–170.

[20] M. Jannesari and B. Omoomi, The metric dimension of the lexicographic product of graphs, Discrete Math. 312 (2012) 3349–3356. doi:10.1016/j.disc.2012.07.025

[21] J.A. Rodríguez-Velázquez, C. García Gómez and G.A. Barragán-Ramírez, Computing the local metric dimension of a graph from the local metric dimension of primary subgraphs, Int. J. Comput. Math. 92 (2015) 686–693. doi:10.1080/00207160.2014.918608

[22] J.A. Rodríguez-Velázquez, D. Kuziak, I.G. Yero and J.M. Sigarreta, The metric dimension of strong product graphs, Carpathian J. Math. 31 (2015) 261–268.

[23] S.W. Saputro, R. Simanjuntak, S. Uttunggadewa, H. Assiyatun, E.T. Baskoro, A.N.M. Salman and M. Bača, The metric dimension of the lexicographic product of graphs, Discrete Math. 313 (2013) 1045–1051. doi:10.1016/j.disc.2013.01.021

[24] A.J. Schwenk, Computing the characteristic polynomial of a graph, Lecture Notes in Math. 406 (1974) 153–172. doi:10.1007/BFb0066438

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

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

[27] P.J. Slater, Dominating and reference sets in a graph, J. Math. Phys. Sci. 22 (1988) 445–455.

[28] I.G. Yero, D. Kuziak and J.A. Rodríquez-Velázquez, On the metric dimension of corona product graphs, Comput. Math. Appl. 61 (2011) 2793–2798. doi:10.1016/j.camwa.2011.03.046