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 .

The general position problem asks for large sets of vertices such that no three vertices of the set lie on a common shortest path. Recently a dynamic version of this problem was defined, called the mobile general position problem , in which a collection of robots must visit all the vertices of the graph whilst remaining in general position. In this paper we investigate this problem in the context of Cartesian products, corona products and joins, giving upper and lower bounds for general graphs and exact values for families including grids, cylinders, Hamming graphs and prisms of trees.

Let G be a graph and X⊆V(G). Then X is a mutual-visibility set if each pair of vertices from X is connected by a geodesic with no internal vertex in X. The mutual-visibility number μ(G) of G is the cardinality of a largest mutual-visibility set. In this paper, the mutual-visibility number of strong product graphs is investigated. As a tool for this, total mutual-visibility sets are introduced. Along the way, basic properties of such sets are presented. The (total) mutual-visibility number of strong products is bounded from below in two ways, and determined exactly for strong grids of arbitrary dimension. Strong prisms are studied separately and a couple of tight bounds for their mutual-visibility number are given.

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.

If X is a subset of vertices of a graph G, then vertices u and v are X-visible if there exists a shortest u,v-path P such that V(P)∩X⊆{u,v}. If each two vertices from X are X-visible, then X is a mutual-visibility set. The mutual-visibility number of G is the cardinality of a largest mutual-visibility set of G and has been already investigated. In this paper a variety of mutual-visibility problems is introduced based on which natural pairs of vertices are required to be X-visible. This yields the total, the dual, and the outer mutual-visibility numbers. We first show that these graph invariants are related to each other and to the classical mutual-visibility number, and then we prove that the three newly introduced mutual-visibility problems are computationally difficult. According to this result, we compute or bound their values for several graphs classes that include for instance grid graphs and tori. We conclude the study by presenting some inter-comparison between the values of such parameters, which is based on the computations we made for some specific families.

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.

Abstract Let $(X,d)$ be a metric space. A set $S\subseteq X$ is said to be a $k$-metric generator for $X$ if and only if for any pair of different points $u,v\in X$, there exist at least $k$ points $w_1,w_2, \ldots w_k\in S$ such that $d(u,w_i)\ne d(v,w_i),\; \textrm{for all}\; i\in \{1, \ldots k\}.$ Let $\mathcal{R}_k(X)$ be the set of metric generators for $X$. The $k$-metric dimension $\dim _k(X)$ of $(X,d)$ is defined as $$\begin{equation*}\dim_k(X)=\inf\{|S|:\, S\in \mathcal{R}_k(X)\}.\end{equation*}$$Here, we discuss the $k$-metric dimension of $(V,d_t)$, where $V$ is the set of vertices of a simple graph $G$ and the metric $d_t:V\times V\rightarrow \mathbb{N}\cup \{0\}$ is defined by $d_t(x,y)=\min \{d(x,y),t\}$ from the geodesic distance $d$ in $G$ and a positive integer $t$. The case $t\ge D(G)$, where $D(G)$ denotes the diameter of $G$, corresponds to the original theory of $k$-metric dimension, and the case $t=2$ corresponds to the theory of $k$-adjacency dimension. Furthermore, this approach allows us to extend the theory of $k$-metric dimension to the general case of non-necessarily connected graphs. Finally, we analyse the computational complexity of determining the $k$-metric dimension of $(V,d_t)$ for the metric $d_t$.

A subset D of vertices of a graph G is a total dominating set if every vertex of G is adjacent to at least one vertex of D. The total dominating set D is called a total co-independent dominating set if the subgraph induced by V−D is edgeless and has at least one vertex. The minimum cardinality of any total co-independent dominating set is the total co-independent domination number of G and is denoted by γt,coi(G)⁠. In this work we study some complexity and combinatorial properties of γt,coi(G)⁠. Specifically, we prove that deciding whether γt,coi(G)≤k for a given integer k is an NP-complete problem and give several bounds on γt,coi(G)⁠. Moreover, since any total co-independent dominating set is a total dominating set, we characterize all the trees having equal total co-independent domination number and total domination number.

Let G=(V,E) be a simple connected graph and S={w1,…,wt}⊆V an ordered subset of vertices. The metric representation of a vertex u∈V with respect to S is the t -vector r(u|S)=(dG(u,w1),…,dG(u,wt)) , where dG(u,v) represents the length of a shortest u−v path in G . A set S is a k -antiresolving set if k is the largest positive integer such that for every vertex v∈V−S there exist other k−1 different vertices v1,…,vk−1∈V−S such that v,v1,…,vk−1 have the same metric representation with respect to S . The k -metric antidimension of G is the minimum cardinality among all the k -antiresolving sets for G , and G is k -metric antidimensional if k is the largest integer such that G contains a k -antiresolving set. In this article, we provide characterizations for 1-metric antidimensional trees and unicyclic graphs, together with computationally efficient algorithms to decide whether these types of graphs are 1-metric antidimensional.

A vertex w of a connected graph G strongly resolves two vertices u, v ∈ V ( G), if there exists some shortest u – w path containing v or some shortest v – w path containing u. A set S of vertices is a strong metric generator for G if every pair of vertices of G is strongly resolved by some vertex of S. The smallest cardinality of a strong metric generator for G is called the strong metric dimension of G. In this paper we obtain several tight bounds or closed formulae for the strong metric dimension of the Cartesian sum of graphs in terms of the strong metric dimension, clique number or twins-free clique number of its factor graphs.