Displaying similar documents to “On Optimal Realizations of Finite Metric Spaces by Graphs.”

Computing the Metric Dimension of a Graph from Primary Subgraphs

Dorota Kuziak, Juan A. Rodríguez-Velázquez, Ismael G. Yero (2017)

Discussiones Mathematicae Graph Theory

Similarity:

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...

Closed Formulae for the Strong Metric Dimension of Lexicographi

Dorota Kuziak, Ismael G. Yero, Juan A. Rodríguez-Velázquez (2016)

Discussiones Mathematicae Graph Theory

Similarity:

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...

On the strong metric dimension of the strong products of graphs

Dorota Kuziak, Ismael G. Yero, Juan A. Rodríguez-Velázquez (2015)

Open Mathematics

Similarity:

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...

On metric σ-discrete spaces

Szymon Plewik, Marta Walczyńska (2016)

Banach Center Publications

Similarity:

By studying dimensional types of metric scattered spaces, we consider the wider class of metric σ-discrete spaces. Applying techniques relevant to this wider class, we present new proofs of some embeddable properties of countable metric spaces in such a way that they can be generalized onto uncountable metric scattered spaces. Related topics are also explored, which gives a few new results.