- Tytuł:
- Computing the Metric Dimension of a Graph from Primary Subgraphs
- Autorzy:
-
Kuziak, Dorota
Rodríguez-Velázquez, Juan A.
Yero, Ismael G. - Powiązania:
- https://bibliotekanauki.pl/articles/31342126.pdf
- Data publikacji:
- 2017-02-01
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
metric dimension
metric basis
primary subgraphs
rooted product graphs
corona product graphs - Opis:
- 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.
- Źródło:
-
Discussiones Mathematicae Graph Theory; 2017, 37, 1; 273-293
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł