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 .

A metric basis in a graph G is a smallest possible set S of vertices of G, with the property that any two vertices of G are uniquely recognized by using a vector of distances to the vertices in S. A strong metric basis is a variant of metric basis that represents a smallest possible set S′ of vertices of G such that any two vertices x,y of G are uniquely recognized by a vertex v∈S′ by using either a shortest x−v path that contains y, or a shortest y−v path that contains x. Given a graph G, there exist sometimes some vertices of G such that they forcedly belong to every metric basis or to every strong metric basis of G. Such vertices are called (resp. strong) basis forced vertices in G. It is natural to consider finding them, in order to find a (strong) metric basis in a graph. However, deciding about the existence of these vertices in arbitrary graphs is in general an NP-hard problem, which makes desirable the problem of searching for (strong) basis forced vertices in special graph classes. This article centres the attention in the class of unicyclic graphs. It is known that a unicyclic graph can have at most two basis forced vertices. In this sense, several results aimed to classify the unicyclic graphs according to the number of basis forced vertices they have are given in this work. On the other hand, with respect to the strong metric bases, it is proved in this work that unicyclic graphs can have as many strong basis forced vertices as we would require. Moreover, some characterizations of the unicyclic graphs concerning the existence or not of such vertices are given in the exposition as well.

This investigation is firstly focused into showing that two metric parameters represent the same object in graph theory. That is, we prove that the multiset resolving sets and the ID-colorings of graphs are the same thing. We also consider some computational and combinatorial problems of the multiset dimension, or equivalently, the ID-number of graphs. We prove that the decision problem concerning finding the multiset dimension of graphs is NP-complete. We consider the multiset dimension of king grids and prove that it is bounded above by 4. We also give a characterization of the strong product graphs with one factor being a complete graph, and whose multiset dimension is not infinite.

A set R⊆V(G) is a resolving set of a graph G if for all distinct vertices v,u∈V(G) there exists an element r∈R such that d(r,v)≠d(r,u). The metric dimension dim(G) of the graph G is the cardinality of a smallest resolving set of G. A resolving set with cardinality dim(G) is called a metric basis of G. We consider vertices that are in all metric bases, and we call them basis forced vertices. We give several structural properties of sparse and dense graphs where basis forced vertices are present. In particular, we give bounds for the maximum number of edges in a graph containing basis forced vertices. Our bound is optimal whenever the number of basis forced vertices is even. Moreover, we provide a method of constructing fairly sparse graphs with basis forced vertices. We also study vertices which are in no metric basis in connection to cut-vertices and pendants. Furthermore, we show that deciding whether a vertex is in all metric bases is co-NP-hard, and deciding whether a vertex is in no metric basis is NP-hard.

A subset S of vertices is a resolving set in a graph if every vertex has a unique array of distances to the vertices of S. Consequently, we can locate any vertex of the graph with the aid of the distance arrays. The problem of finding the smallest cardinality of a resolving set in a graph has been widely studied over the years. In this paper, we consider sets S which can locate several, say up to ℓ, vertices in a graph. These sets are called {ℓ}-resolving sets and the smallest cardinality of such a set is the {ℓ}-metric dimension of the graph. In this paper, we will give the {ℓ}-metric dimensions for trees and king grids. We will show that there are certain vertices that necessarily belong to an {ℓ}-resolving set. Moreover, we will classify all graphs whose {ℓ}-metric dimension equals ℓ.