|
| | | | |
| | | |
| Stat |
Members: 3666
Articles: 2'599'751
Articles rated: 2609
05 February 2025 |
|
| | | | |
|
Article overview
| |
|
|
Resolving vertices of graphs with differences | | Iztok Peterina
; Jelena Sedlar
; Riste Škrekovski
; Ismael G. Yero
; | | Date: |
2 Sep 2023 | | Abstract: | The classical (vertex) metric dimension of a graph G is defined as the
cardinality of a smallest set S in V (G) such that any two vertices x and y
from G have different distances to least one vertex from S: The k-metric
dimension is a generalization of that notion where it is required that any pair
of vertices has different distances to at least k vertices from S: In this
paper, we introduce the weak k-metric dimension of a graph G; which is defined
as the cardinality of a smallest set of vertices S such that the sum of the
distance differences from any pair of vertices to all vertices of S is at least
k: This dimension is "stronger" than the classical metric dimension, yet
"weaker" than k-metric dimension, and it can be formulated as an ILP problem.
The maximum k for which the weak k-metric dimension is defined is denoted by
kappa(G). We first prove several properties of the weak k-metric dimension
regarding the presence of true or false twin vertices in a graph. Using those
properties, the kappa(G) is found for some basic graph classes, such as paths,
stars, cycles, and complete (bipartite) graphs. We also find kappa(G) for trees
and grid graphs using the observation that the distance difference increases by
the increase of the cardinality of a set S. For all these graph classes we
further establish the exact value of the weak k-metric dimension for all k <=
kappa(G). | | Source: | arXiv, 2309.00922 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
|
| |
|
|
|
REGISTER