A1 Refereed original research article in a scientific journal

On the vertices belonging to all edge metric bases




AuthorsHakanen, Anni; Junnila, Ville; Laihonen, Tero; Yero, Ismael G.

PublisherELSEVIER

Publication year2026

JournalDiscrete Applied Mathematics

Volume379

First page 339

Last page354

ISSN0166-218X

eISSN1872-6771

DOIhttps://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 addresshttps://research.utu.fi/converis/portal/detail/Publication/500356111


Abstract

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.
This reprint may differ from the original in pagination and typographic detail. Please cite the original version.




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.


Last updated on 2025-30-09 at 11:36