Vertaisarvioitu alkuperäisartikkeli tai data-artikkeli tieteellisessä aikakauslehdessä (A1)

On Vertices Contained in All or in No Metric Basis




Julkaisun tekijätHakanen Anni, Junnila Ville, Laihonen Tero, Yero Ismael G.

KustantajaElsevier BV

Julkaisuvuosi2021

JournalDiscrete Applied Mathematics

eISSN1872-6771

DOIhttp://dx.doi.org/10.1016/j.dam.2021.12.004

Verkko-osoitehttps://www.sciencedirect.com/science/article/pii/S0166218X21004820?via%3Dihub

Rinnakkaistallenteen osoitehttps://research.utu.fi/converis/portal/detail/Publication/68601224


Tiivistelmä

A set RV (G) is a resolving set of a graph G if for all distinct vertices v, uV (G) there exists an element rR 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. 


Ladattava julkaisu

This is an electronic reprint of the original article.
This reprint may differ from the original in pagination and typographic detail. Please cite the original version.




Ladattava julkaisu

This is an electronic reprint of the original article.
This reprint may differ from the original in pagination and typographic detail. Please cite the original version.




Last updated on 2022-07-04 at 16:21