A1 Refereed original research article in a scientific journal
On the vertices belonging to all edge metric bases
Authors: Hakanen, Anni; Junnila, Ville; Laihonen, Tero; Yero, Ismael G.
Publisher: ELSEVIER
Publication year: 2026
Journal: Discrete Applied Mathematics
Volume: 379
First page : 339
Last page: 354
ISSN: 0166-218X
eISSN: 1872-6771
DOI: https://doi.org/10.1016/j.dam.2025.08.054
Web address : https://doi.org/10.1016/j.dam.2025.08.054
Self-archived copy’s web address: 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.
Downloadable publication This is an electronic reprint of the original article. |
Funding information in the publication:
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.