Mostrar el registro sencillo del ítem

dc.contributor.authorHakanen, Anni
dc.contributor.authorJunnila, Ville
dc.contributor.authorLaihonen, Tero
dc.contributor.authorGonzález Yero, Ismael 
dc.contributor.otherMatemáticases_ES
dc.date.accessioned2023-09-29T10:46:53Z
dc.date.available2023-09-29T10:46:53Z
dc.date.issued2021-12-21
dc.identifier.issn0166-218X
dc.identifier.urihttp://hdl.handle.net/10498/29356
dc.description.abstractA set R⊆V(G) is a resolving set of a graph G if for all distinct vertices v,u∈V(G) there exists an element r∈R such that d(r,v)≠d(r,u). The metric dimension dim(G) of the graph G is the cardinality of a smallest resolving set of G. A resolving set with cardinality dim(G) is called a metric basis of G. We consider vertices that are in all metric bases, and we call them basis forced vertices. We give several structural properties of sparse and dense graphs where basis forced vertices are present. In particular, we give bounds for the maximum number of edges in a graph containing basis forced vertices. Our bound is optimal whenever the number of basis forced vertices is even. Moreover, we provide a method of constructing fairly sparse graphs with basis forced vertices. We also study vertices which are in no metric basis in connection to cut-vertices and pendants. Furthermore, we show that deciding whether a vertex is in all metric bases is co-NP-hard, and deciding whether a vertex is in no metric basis is NP-hard.es_ES
dc.formatapplication/pdfes_ES
dc.language.isoenges_ES
dc.publisherElsevieres_ES
dc.rightsAtribución 4.0 Internacional*
dc.rights.urihttp://creativecommons.org/licenses/by/4.0/*
dc.sourceDiscrete Applied Mathematics. Vol. 319, 15 October 2022, pp. 407-423es_ES
dc.subjectCut-vertexes_ES
dc.subjectForced vertexes_ES
dc.subjectMetric basises_ES
dc.subjectMetric dimensiones_ES
dc.subjectNP-hardes_ES
dc.subjectPendantes_ES
dc.subjectResolving setes_ES
dc.subjectUnicyclic graphes_ES
dc.titleOn vertices contained in all or in no metric basises_ES
dc.typejournal articlees_ES
dc.rights.accessRightsopen accesses_ES
dc.description.physDesc17 páginases_ES
dc.identifier.doi10.1016/j.dam.2021.12.004
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