A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä

On the vertices belonging to all edge metric bases




TekijätHakanen, Anni; Junnila, Ville; Laihonen, Tero; Yero, Ismael G.

KustantajaELSEVIER

Julkaisuvuosi2026

Lehti: Discrete Applied Mathematics

Vuosikerta379

Aloitussivu339

Lopetussivu354

ISSN0166-218X

eISSN1872-6771

DOIhttps://doi.org/10.1016/j.dam.2025.08.054

Julkaisun avoimuus kirjaamishetkelläAvoimesti saatavilla

Julkaisukanavan avoimuus Osittain avoin julkaisukanava

Verkko-osoitehttps://doi.org/10.1016/j.dam.2025.08.054

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


Tiivistelmä

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




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.


Last updated on 2025-16-10 at 11:26