Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: metric dimension

Sortuj według:

Ogranicz wyniki do:

Computing the Metric Dimension of a Graph from Primary Subgraphs

100%

Kuziak D., Rodríguez-Velázquez J. A., Yero I. G.

Discussiones Mathematicae Graph Theory

2017

tom 37

nr 1

273-293

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.

Weak Total Resolvability In Graphs

86%

Casel K., Estrada-Moreno A., Fernau H., Rodríguez-Velázquez J. A.

Discussiones Mathematicae Graph Theory

2016

tom 36

nr 1

185-210

A vertex v ∈ V (G) is said to distinguish two vertices x, y ∈ V (G) of a graph G if the distance from v to x is di erent from the distance from v to y. A set W ⊆ V (G) is a total resolving set for a graph G if for every pair of vertices x, y ∈ V (G), there exists some vertex w ∈ W − {x, y} which distinguishes x and y, while W is a weak total resolving set if for every x ∈ V (G)−W and y ∈ W, there exists some w ∈ W −{y} which distinguishes x and y. A weak total resolving set of minimum cardinality is called a weak total metric basis of G and its cardinality the weak total metric dimension of G. Our main contributions are the following ones: (a) Graphs with small and large weak total metric bases are characterised. (b) We explore the (tight) relation to independent 2-domination. (c) We introduce a new graph parameter, called weak total adjacency dimension and present results that are analogous to those presented for weak total dimension. (d) For trees, we derive a characterisation of the weak total (adjacency) metric dimension. Also, exact figures for our parameters are presented for (generalised) fans and wheels. (e) We show that for Cartesian product graphs, the weak total (adjacency) metric dimension is usually pretty small. (f) The weak total (adjacency) dimension is studied for lexicographic products of graphs.

Ograniczanie wyników

2 Discussiones Mathematicae Graph Theory

2 Rodríguez-Velázquez J. A.

1 Casel K.

1 Estrada-Moreno A.

1 Fernau H.

1 Kuziak D.

1 Yero I. G.

1 2017

1 2016

Wyniki wyszukiwania

Computing the Metric Dimension of a Graph from Primary Subgraphs

Weak Total Resolvability In Graphs