Domination-type parameters are difficult to manage in Cartesian product graphs and there is usually no general relationship between the parameter in both factors and in the product graph. This is the situation of the domination number, the Roman domination number or the $2$-domination number, among others. Contrary to what happens with the domination number and the Roman domination number, the $2$-domination number remains unknown in cylinders, that is, the Cartesian product of a cycle and a path and in this paper, we will compute this parameter in the cylinders with small cycles. We will develop two algorithms involving the $(\min,+)$ matrix product that will allow us to compute the desired values of $\gamma_2(C_n\Box P_m)$, with $3\leq n\leq 15$ and $m\geq 2$. We will also pose a conjecture about the general formulae for the $2$-domination number in this graph class. Comment: 15 pages, 1 figure

Abstract The computation of the domination-type parameters is a challenging problem in Cartesian product graphs. We present an algorithmic method to compute the 2-domination number of the Cartesian product of a path with small order and any cycle, involving the $$(\min ,+)$$ ( min , + ) matrix product. We establish some theoretical results that provide the algorithms necessary to compute that parameter, and the main challenge to run such algorithms comes from the large size of the matrices used, which makes it necessary to improve the techniques to handle these objects. We analyze the performance of the algorithms on modern multicore CPUs and on GPUs and we show the advantages over the sequential implementation. The use of these platforms allows us to compute the 2-domination number of cylinders such that their paths have at most 12 vertices.

A set of vertices S resolves a graph G if every vertex is uniquely determined by its vector of distances to the vertices in S. The metric dimension of G is the minimum cardinality of a resolving set of G. This paper studies the metric dimension of cartesian products $G\,\square\,H$. We prove that the metric dimension of $G\,\square\,G$ is tied in a strong sense to the minimum order of a so‐called doubly resolving set in G. Using bounds on the order of doubly resolving sets, we establish bounds on $G\,\square\,H$ for many examples of G and H. One of our main results is a family of graphs G with bounded metric dimension for which the metric dimension of $G\,\square\,G$ is unbounded.