Autor segons l'article: Kuziak, Dorota; Rodriguez-Velazquez, Juan A; Yero, Ismael G
Departament: Enginyeria Informàtica i Matemàtiques
Autor/s de la URV: Rodríguez Velázquez, Juan Alberto
Paraules clau: Rooted product graphs Primary subgraphs Metric dimension Metric basis Corona product graphs
Resum: 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.
Àrees temàtiques: Mathematics Matemática / probabilidade e estatística Discrete mathematics and combinatorics Ciência da computação Applied mathematics
Accès a la llicència d'ús: https://creativecommons.org/licenses/by/3.0/es/
Adreça de correu electrònic de l'autor: juanalberto.rodriguez@urv.cat
Identificador de l'autor: 0000-0002-9082-7647
Data d'alta del registre: 2024-10-26
Versió de l'article dipositat: info:eu-repo/semantics/publishedVersion
Enllaç font original: https://www.dmgt.uz.zgora.pl/publish/volume.php?volume=37_1
URL Document de llicència: https://repositori.urv.cat/ca/proteccio-de-dades/
Referència a l'article segons font original: Discussiones Mathematicae Graph Theory. 37 (1): 273-293
Referència de l'ítem segons les normes APA: Kuziak, Dorota; Rodriguez-Velazquez, Juan A; Yero, Ismael G (2017). Computing the metric dimension of a graph from primary subgraphs. Discussiones Mathematicae Graph Theory, 37(1), 273-293. DOI: 10.7151/dmgt.1934
DOI de l'article: 10.7151/dmgt.1934
Entitat: Universitat Rovira i Virgili
Any de publicació de la revista: 2017
Tipus de publicació: Journal Publications