Wyniki wyszukiwania - Biblioteka Nauki

Nowa wersja platformy, zawierająca wyłącznie zasoby pełnotekstowe, jest już dostępna.
Przejdź na https://bibliotekanauki.pl

Ograniczanie wyników

Znaleziono wyników: 4

Liczba wyników na stronie

Wyniki wyszukiwania

Sortuj według:

Ogranicz wyniki do:

Closed Formulae for the Strong Metric Dimension of Lexicographi

100%

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

Discussiones Mathematicae Graph Theory

2016

tom 36

nr 4

1051-1064

Given a connected graph G, a vertex w ∈ V (G) strongly resolves two vertices u, v ∈ V (G) if there exists some shortest u − w path containing v or some shortest v − w path containing u. A set S of vertices is a strong metric generator for G if every pair of vertices of G is strongly resolved by some vertex of S. The smallest cardinality of a strong metric generator for G is called the strong metric dimension of G. In this paper we obtain several relationships between the strong metric dimension of the lexicographic product of graphs and the strong metric dimension of its factor graphs.

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.

Erratum to “On the strong metric dimension of the strong products of graphs”

100%

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

Open Mathematics

2015

tom 13

nr 1

The original version of the article was published in Open Mathematics (formerly Central European Journal of Mathematics) 13 (2015) 64–74. Unfortunately, the original version of this article contains a mistake: in Lemma 2.17 appears that for any C1-graph G and any graph H, β (G ⊠ H) ≤ β (G)(β(H)+1), while should be β (G ⊠ H) ≤ β(H) (β(G)+1). In this erratum we correct the lemma, its proof and some of its consequences.

On the strong metric dimension of the strong products of graphs

100%

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

Open Mathematics

2015

tom 13

nr 1

Let G be a connected graph. A vertex w ∈ V.G/ strongly resolves two vertices u,v ∈ V.G/ if there exists some shortest u-w path containing v or some shortest v-w path containing u. A set S of vertices is a strong resolving set for G if every pair of vertices of G is strongly resolved by some vertex of S. The smallest cardinality of a strong resolving set for G is called the strong metric dimension of G. It is well known that the problem of computing this invariant is NP-hard. In this paper we study the problem of finding exact values or sharp bounds for the strong metric dimension of strong product graphs and express these in terms of invariants of the factor graphs.