A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä
On the vertices belonging to all edge metric bases
Tekijät: Hakanen, Anni; Junnila, Ville; Laihonen, Tero; Yero, Ismael G.
Kustantaja: ELSEVIER
Julkaisuvuosi: 2026
Lehti: Discrete Applied Mathematics
Vuosikerta: 379
Aloitussivu: 339
Lopetussivu: 354
ISSN: 0166-218X
eISSN: 1872-6771
DOI: https://doi.org/10.1016/j.dam.2025.08.054
Julkaisun avoimuus kirjaamishetkellä: Avoimesti saatavilla
Julkaisukanavan avoimuus : Osittain avoin julkaisukanava
Verkko-osoite: https://doi.org/10.1016/j.dam.2025.08.054
Rinnakkaistallenteen osoite: https://research.utu.fi/converis/portal/detail/Publication/500356111
An edge metric basis of a connected graph G is a smallest possible set of vertices S of G satisfying the following: for any two edges e, f of G there is a vertex s E S such that the distances from s to e and f differ. The cardinality of an edge metric basis is the edge metric dimension of G. In this article we consider the existence of vertices in a graph G such that they must belong to each edge metric basis of G, and we call them edge basis forced vertices. On the other hand, we name edge void vertices those vertices which do not belong to any edge metric basis. Among other results, we first deal with the computational complexity of deciding whether a given vertex is an edge basis forced vertex or an edge void vertex. We also establish some tight bounds on the number of edge basis forced vertices of a graph, as well as, on the number of edges in a graph having at least one edge basis forced vertex. Moreover, we show some realization results concerning which values for the integers n, k and f allow to confirm the existence of a graph G with n vertices, f edge basis forced vertices and edge metric dimension k.
Ladattava julkaisu This is an electronic reprint of the original article. |
Julkaisussa olevat rahoitustiedot:
Ismael G. Yero has been partially supported by the Spanish Ministry of Science and Innovation through the grant PID2023-146643NB-I00. Anni Hakanen, Ville Junnila and Tero Laihonen have been partially supported by Research Council of Finland grant number 338797.