Mostrar el registro sencillo del ítem

dc.contributor.authorPeterin, I.
dc.contributor.authorSedlar, J.
dc.contributor.authorŠkrekovski, R.
dc.contributor.authorGonzález Yero, Ismael 
dc.contributor.otherMatemáticases_ES
dc.date.accessioned2024-10-21T09:47:50Z
dc.date.available2024-10-21T09:47:50Z
dc.date.issued2024
dc.identifier.issn1807-0302
dc.identifier.issn2238-3603
dc.identifier.urihttp://hdl.handle.net/10498/33683
dc.description.abstractThe classical (vertex) metric dimension of a graph G is defined as the cardinality of a smallest set S⊆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 κ(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 κ(G) is found for some basic graph classes, such as paths, stars, cycles, and complete (bipartite) graphs. We also find κ(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≤κ(G).es_ES
dc.description.sponsorshipEuropean Commission (European Union) European Regional Development Fund (European Union) Ministerio de Ciencia e Innovación (España) Javna Agencija za Raziskovalno Dejavnost RS (Slovenia)es_ES
dc.formatapplication/pdfes_ES
dc.language.isoenges_ES
dc.publisherSpringer Naturees_ES
dc.rightsAtribución 4.0 Internacional*
dc.rights.urihttp://creativecommons.org/licenses/by/4.0/*
dc.sourceComputational and Applied Mathematics - 2024, Vol. 43 n.5 pp. 1-22es_ES
dc.subject05C12es_ES
dc.subjectWeak k-metric dimensiones_ES
dc.subjectWeak k-resolving setes_ES
dc.titleResolving vertices of graphs with differenceses_ES
dc.typejournal articlees_ES
dc.rights.accessRightsopen accesses_ES
dc.description.physDesc22 páginases_ES
dc.identifier.doi10.1007/s40314-024-02806-3
dc.relation.projectIDinfo:eu-repo/grantAgreement/AEI/Plan Estatal de Investigación Científica y Técnica y de Innovación 2017-2020/PID2019-105824GB-I00/ES/OPTIMIZACION MATEMATICA Y COMBINATORIA EN REDES/ es_ES
dc.type.hasVersionVoRes_ES


Ficheros en el ítem

Este ítem aparece en la(s) siguiente(s) colección(ones)

Mostrar el registro sencillo del ítem

Atribución 4.0 Internacional
Esta obra está bajo una Licencia Creative Commons Atribución 4.0 Internacional