Pełnotekstowe zasoby PLDML oraz innych baz dziedzinowych są już dostępne w nowej Bibliotece Nauki.
Zapraszamy na https://bibliotekanauki.pl
Preferencje help
Polish version English version Język
Widoczny [Schowaj] Abstrakt
Liczba wyników

Znaleziono wyników: 5

Liczba wyników na stronie
first rewind previous Strona / 1 next fast forward last

Wyniki wyszukiwania

help Sortuj według:

help Ogranicz wyniki do:
first rewind previous Strona / 1 next fast forward last
1
Content available remote

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
EN
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.
2
Content available remote

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
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.
3
Content available remote

Bounding the Openk-Monopoly Number of Strong Product Graphs

100%
Kuziak D., Peterin I., Yero I. G.
Discussiones Mathematicae Graph Theory
|
2017
|
tom 38
|
nr 1
287-299
EN
Let G = (V, E) be a simple graph without isolated vertices and minimum degree δ, and let k ∈ {1 − ⌈δ/2⌉, . . . , ⌊δ/2⌋} be an integer. Given a set M ⊂ V, a vertex v of G is said to be k-controlled by M if [...] δM(v)≥δG(v)2+k $\delta _M (v) \ge {{\delta _G (v)} \over 2} + k$ , where δM(v) represents the number of neighbors of v in M and δG(v) the degree of v in G. A set M is called an open k-monopoly if every vertex v of G is k-controlled by M. The minimum cardinality of any open k-monopoly is the open k-monopoly number of G. In this article we study the open k-monopoly number of strong product graphs. We present general lower and upper bounds for the open k-monopoly number of strong product graphs. Moreover, we study in addition the open 0-monopolies of several specific families of strong product graphs.
4
Content available remote

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
EN
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.
5
Content available remote

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
EN
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.
first rewind previous Strona / 1 next fast forward last
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ć.