RT journal article
T1 On vertices contained in all or in no metric basis
A1 Hakanen, Anni
A1 Junnila, Ville
A1 Laihonen, Tero
A1 González Yero, Ismael
A2 Matemáticas
K1 Cut-vertex
K1 Forced vertex
K1 Metric basis
K1 Metric dimension
K1 NP-hard
K1 Pendant
K1 Resolving set
K1 Unicyclic graph
AB A 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.
PB Elsevier
SN 0166-218X
YR 2021
FD 2021-12-21
LK http://hdl.handle.net/10498/29356
UL http://hdl.handle.net/10498/29356
LA eng
DS Repositorio Institucional de la Universidad de Cádiz
RD 12-nov-2026