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/