Computing the Metric Dimension of a Graph from Primary Subgraphs

• Autorzy: Dorota Kuziak , Juan A. Rodríguez-Velázquez , Ismael G. Yero
• 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.

Słowa kluczowe

EN

metric dimension; metric basis; primary subgraphs; rooted product graphs; corona product graphs

Kategorie tematyczne

• 05C12: Distance in graphs
• 05C76: Graph operations (line graphs, products, etc.)

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2017
• Tom: 37
• Numer: 1
• Strony: 273-293

Daty

wydano

2017-02-01

otrzymano

2015-07-14

poprawiono

2016-04-30

zaakceptowano

2016-04-30

online

2017-01-13

Twórcy

autor

Dorota Kuziak

• Departament d’Enginyeria Informàtica i Matemàtiques, Universitat Rovira i Virgili, Av. Països Catalans 26, 43007 Tarragona,

autor

Juan A. Rodríguez-Velázquez

• Departament d’Enginyeria Informàtica i Matemàtiques, Universitat Rovira i Virgili, Av. Països Catalans 26, 43007 Tarragona,

autor

Ismael G. Yero

• Departamento de Matemáticas, Escuela Politécnica Superior, Universidad de Cádiz, Av. Ramón Puyol s/n, 11202 Algeciras,

Identyfikatory

DOI

10.7151/dmgt.1934