PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2017 | 37 | 1 | 273-293
Tytuł artykułu

Computing the Metric Dimension of a Graph from Primary Subgraphs

Treść / Zawartość
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
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.
Wydawca
Rocznik
Tom
37
Numer
1
Strony
273-293
Opis fizyczny
Daty
wydano
2017-02-01
otrzymano
2015-07-14
poprawiono
2016-04-30
zaakceptowano
2016-04-30
online
2017-01-13
Twórcy
  • Departament d’Enginyeria Informàtica i Matemàtiques, Universitat Rovira i Virgili, Av. Països Catalans 26, 43007 Tarragona,, dorota.kuziak@urv.cat
  • Departament d’Enginyeria Informàtica i Matemàtiques, Universitat Rovira i Virgili, Av. Països Catalans 26, 43007 Tarragona,, juanalberto.rodriguez@urv.cat
  • Departamento de Matemáticas, Escuela Politécnica Superior, Universidad de Cádiz, Av. Ramón Puyol s/n, 11202 Algeciras,, ismael.gonzalez@uca.es
Bibliografia
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.doi-10_7151_dmgt_1934
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.