On the vertices belonging to all edge metric bases

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 ∈ 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.