Efficient Location of Resources in Cylindrical Networks

Abstract

The location of resources in a network satisfying some optimization property is a classical combinatorial problem that can be modeled and solved by using graphs. Key tools in this problem are the domination-type properties, which have been defined and widely studied in different types of graph models, such as undirected and directed graphs, finite and infinite graphs, simple graphs and hypergraphs. When the required optimization property is that every node of the network must have access to exactly one node with the desired resource, the appropriate models are the efficient dominating sets. However, the existence of these vertex sets is not guaranteed in every graph, so relaxing some conditions is necessary to ensure the existence of some kind of dominating sets, as efficient as possible, in a larger number of graphs. In this paper, we study independent $[1,2]$-sets, a generalization of efficient dominating sets defined by Chellali et al., in the case of cylindrical networks. It is known that efficient dominating sets exist in very special cases of cylinders, but the particular symmetry of these graphs will allow us to provide regular patterns that guarantee the existence of independent $[1,2]$-sets in every cylinder, except in one single case, and to compute exact values of the optimal parameter, the independent $[1,2]$-number, in cylinders of selected sizes.

1. Introduction

Graphs have been used, since their informal beginnings, as a model to represent complex networks, to describe different properties within them and to find solutions to diverse problems, such as optimal routes or the best location of resources. Formally, a finite graph is a pair $G=(V,E)$, where V is a non-empty finite set, whose elements are called vertices, and $E\subseteq V\times V$ is a set of unordered pairs of vertices called edges. If $uv$ is an edge, we say that u and v are neighbors. The distance between two vertices u and v in a graph is the number of edges in a shortest path connecting them and it is denoted by $d(u,v)$. The open neighborhood of a vertex u in a graph G is $N\left(u\right)=\{v\in V(G):uv\in E(G\left)\right\}$ and the closed neighborhood is $N\left[u\right]=N\left(u\right)\cup \left\{u\right\}$. The degree of a vertex is the cardinality of its open neighborhood.

Domination-type properties in graphs, formally defined in the late 1950s [1] and early 1960s [2], are a good example of how these models can help to represent real world problems and to provide optimal solutions to them. A dominating set in a graph G is a vertex set S such that every vertex not in S has at least one neighbor in S. This classical definition provides a model of resource location in a network, in such a way that every node of the network has access to such a resource. Once this model is formulated, it is an immediate question to find the best possible distribution, which results in the definition of the domination number $\gamma \left(G\right)$ of a graph G, which is the minimum cardinality of a dominating set of G. An extensive compilation of results on this subject can be found in [3], as well as some of its applications such as the planning of school bus routes, the design of computer communication networks, the location of broadcasting stations, social networks modeling and land surveying.

Following this classic pattern, a large number of variants have been defined, which pay attention to different aspects. For instance, k-domination requests at least k neighbors in S for the vertices not in the k-dominating set S and locating-domination asks for $N\left(u\right)\cap S\ne N\left(v\right)\cap S$ for every pair of vertices $u,v\in V\left(G\right)\backslash S$. Another interesting variation consists of considering dominating sets with additional properties, such as connectedness or independence. A vertex set is connected if every two vertices in it can be joined by a sequence of edges consisting of vertices in the set. This model is useful to distribute resources in a network that need to be connected to each other. The opposite point of view is independence. A vertex set is independent if no pair of vertices in it are neighbors. Independent dominating sets have been widely studied, as they provide a model of resource location in cases where such resources should be placed far away from each other.

The most precise way to dominate a graph is the so-called efficient domination. A vertex set S is an efficient dominating set [4], or perfect code [5,6], if S is independent and every vertex not in S has a unique neighbor in S. The idea behind this definition is keeping the domination of each vertex to the minimum, so that vertices in S are dominated just by themselves, and vertices not in S are dominated just once by vertices in S. Clearly, this definition provides a desirable form of domination, which becomes even more interesting with the repeatedly rediscovered result that ensures every efficient dominating set is a minimum dominating set [3]. However, the main problem with efficient dominating sets is that their existence is not guaranteed in every graph. There are well-known graph families that have no efficient dominating sets and, in these cases, a number of relaxations of conditions are possible in order to obtain a dominating set as efficient as possible. In this paper, we focus on one of these relaxed forms, called independent $[1,2]$-sets and defined in [7]. The lower level of requirement of these sets consists of allowing at most two neighbors in the set, for vertices not in it, while keeping independence. Although existence is not guaranteed either in this case, the lesser requirement leads one to think that the family of graphs that possess such sets is larger than in the case of efficient domination. The independent $[1,2]$-number of a graph G was also defined in [7] as the minimum cardinality of an independent $[1,2]$-set, if such sets exist in G, and it is denoted by $i_{[1,2]}\left(G\right)$. The following general relationship among the three mentioned domination parameters can easily be deduced from definitions. Every graph G satisfies the first inequality, while the last one is true for graphs admitting an independent $[1,2]$-set.

$$\gamma \left(G\right)\le i\left(G\right)\le i_{[1,2]}\left(G\right)$$

(1)

Given two graphs, G and H, the Cartesian product of them is the graph $G\square H$ with vertex set $V(G\square H)=V\left(G\right)\times V\left(H\right)$ and edge set defined as follows: $(u_1,v_1)(u_2,v_2)\in E(G\square H)$ if and only if $u_1{u}_2\in E\left(G\right)$, $v_1=v_2$ or $u_1=u_2$, $v_1{v}_2\in E\left(H\right)$. Cartesian product graphs play an interesting role in the domination-type properties, due in part to the well-known Vizing’s Conjecture [8], which states $\gamma (G\square H)\ge \gamma \left(G\right)\gamma \left(H\right)$ for every two graphs G and H. It was formulated in 1968 and is still open.

We study the particular case of cylindrical networks $C_m\square P_n$, which are the Cartesian product of a cycle $C_m$ and a path $P_n$, and our interest comes from the known fact that they have no efficient dominating set, except in one particular case [9]. On the other hand, studying the existence of independent $[1,2]$-sets in cylinders was proposed as an open problem in [7]. Unlike in the case of grids $P_m\square P_n$, the Cartesian product of two paths, where the domination number is completely computed [10], the domination number of the cylinder is unknown in the general case, while formulas for $\gamma (C_m\square P_n)$ have recently been obtained for $m\le 11$ [11] and $m\le 30$ [12]. This makes cylinders a graph family of interest for domination-type properties, in which there is still much to study.

The rest of the paper is organized as follows. In Section 2, we prove that all cylinders have an independent $[1,2]$-set, except the single case of the Cartesian product of the cycle with 5 vertices and the path with 2 vertices, which has no such set. We use the symmetry of the cylindrical graphs to provide regular models of independent $[1,2]$-sets that, in addition, will give an upper bound for the independent $[1,2]$-number. We will also prove that this upper bound is indeed the exact value, in some small cases. In Section 3, we present a modification of a dynamic programming algorithm, originally developed for computing the domination number of grids, to provide information about the independent $[1,2]$-number in cylinders of selected sizes. Depending on the size of the cylinder, this modified algorithm computes the exact value of the parameter or just an upper bound for it. In the latter case we combine these results with an appropriate lower bound, in order to obtain the desired exact value. Finally, in Section 4 and Section 5 we present and discuss the experimental results obtained with the above mentioned algorithm. All graphs that appear in this paper are finite, simple and undirected. For undefined general concepts of graph theory, we refer to [13].

2. Dominating a Cylinder as Efficiently as Possible

We devote this section to studying the existence of independent $[1,2]$-sets in cylinders of any size. As we mentioned before, a cylinder $C_m\square P_n$ is the Cartesian product of a cycle $C_m$ with $m\ge 3$ vertices and a path $P_n$ with $n\ge 2$ vertices. We will not consider the smallest case $C_m\square P_1=C_m$ because all vertices in a cycle have degree two, so that every independent dominating set is trivially an independent $[1,2]$-set.

We present some regular patterns that provide independent $[1,2]$-sets in every cylinder, except in the case $C_5\square P_2$, where no such sets exist. The key point of this graph family is the particular symmetry of cylinders, which allows one to replicate small pieces in order to cover the whole graph.

The interest in obtaining independent $[1,2]$-sets in cylinders lies in the known fact that just a particular case of them have an efficient dominating set, as we recall in the following proposition.

Proposition 1.

[9] The cylinder $C_m\square P_n$ has an efficient dominating set if and only if $m\equiv 0\left(\mathrm{mod}4\right)$ and $n=2$.

We begin our study about the behaviour of independent $[1,2]$-sets in cylinders proving that $C_5\square P_2$ has no such sets. This will eventually be the unique case of a cylinder failing this property.

Proposition 2.

The cylinder $C_5\square P_2$ has no independent $[1,2]$-set.

Proof. 

Denote $V(C_5\square P_2)$ by $\{(u_i,k):1\le i\le 5,1\le k\le 2\}$ and suppose on the contrary that $S\subseteq V(C_5\square P_2)$ is an independent $[1,2]$-set. Suppose that there exist at least two vertices in S sharing the second coordinate. By the symmetry of the graph, we may assume that $(u_i,1),(u_j,1)\in S$.

Note that $d((u_i,1),(u_j,1))\le 2$, so it must be $d((u_i,1),(u_j,1))=2$, because S is independent. By symmetry, we may assume that $u_i=u_1$ and $u_j=u_3$. Then $(u_1,2),(u_2,1),(u_3,2)\notin S$, by independence, so $(u_2,2)\in S$ in order to be dominated. However, this means that $(u_2,1)$ has three neighbors in S, which is not possible (see Figure 1). Therefore, if $(u_i,1)\in S$ then $(u_{i^{\prime }},1)\notin S$ for every $i^{\prime }\ne i$. In the same way, if $(u_j,2)\in S$ then $(u_{j^{\prime }},2)\notin S$ for every $j^{\prime }\ne j$. Finally, $\left|S\right|\le 2$, but $3=\gamma (C_5\square P_2)\le i_{[1,2]}(C_5\square P_2)$, a contradiction. □

We now focus on the rest of the cylinders with $n=2$, where we provide an example of an independent $[1,2]$-set in each size and we also obtain the exact value of the independent $[1,2]$-number.

Proposition 3.

Let $m\ge 3$ be an integer. Then, the cylinder $C_m\square P_2$ has an independent $[1,2]$-set if and only if $m\ne 5$. Moreover,

$$i_{[1,2]}(C_m\square P_2))=i(C_m\square P_2)=\left\{\begin{array}{cc}\lceil \frac{m}{2}\rceil \hfill & ifm\equiv 0,3\left(\mathrm{mod}4\right),\hfill \\ \lceil \frac{m}{2}\rceil +1\hfill & ifm\equiv 1,2\left(\mathrm{mod}4\right),m\ne 5.\hfill \end{array}\right.$$

Proof. 

By Proposition 2, we know that $C_5\square P_2$ has no independent $[1,2]$-set. It is shown in [14] that $i(C_m\square P_2)=\lceil \frac{m}{2}\rceil$, if $m\equiv 0,3\left(\mathrm{mod}4\right)$, and $i(C_m\square P_2)=\lceil \frac{m}{2}\rceil +1$, if $m\equiv 1,2\left(\mathrm{mod}4\right)$. For every integer $m\ne 5$ we will construct an independent $[1,2]$-set, with $i(C_m\square P_2)$ vertices, so we will obtain that $i_{[1,2]}(C_m\square P_2)\le i(C_m\square P_2)$.

If $m\equiv 0\left(\mathrm{mod}4\right)$, then $m=4r\ge 4$ and consider the set of black vertices in Figure 2a. The basic block can be repeated r times to obtain an independent $[1,2]$-set S of $C_{4r}\square P_2$. Each basic block contains 2 vertices of S, so $\left|S\right|=2r=\frac{m}{2}=\lceil \frac{m}{2}\rceil =i(C_m\square P_2)$. Note that S is also an efficient dominating set.

If $5<m\equiv 1\left(\mathrm{mod}4\right)$, then $m=4r+1\ge 9$ and $r\ge 2$. We repeat the basic block $r-2$ times, add the tail block and the rest (see Figure 2b for the case $r=2,m=9$ and Figure 2c for the general case $r\ge 3$). We obtain an independent $[1,2]$-set S (black vertices) with $2(r-2)+6=2r+2=\frac{m-1}{2}+2=\frac{m+1}{2}+1=\lceil \frac{m}{2}\rceil +1=i(C_m\square P_2)$ vertices.

If $m\equiv 2\left(\mathrm{mod}4\right)$, then $m=4r+2\ge 6$ and $r\ge 1$. We add $r-1$ copies of the basic block, the tail block for this case and the appropriate rest (see Figure 2d for the case $r=1,m=6$ and Figure 2e for the general case $r\ge 2$) and we obtain an independent $[1,2]$-set with $2(r-1)+4=2r+2=\frac{m}{2}+1=\lceil \frac{m}{2}\rceil +1=i(C_m\square P_2)$ vertices.

If $m\equiv 3\left(\mathrm{mod}4\right)$, then $m=4r+3\ge 3$ and $r\ge 0$. We construct the independent $[1,2]$-set by adding r copies of the basic block to the rest for this size, as is shown in Figure 2f if $r=0,m=3$ and in Figure 2g if $r\ge 1$. We obtain an independent $[1,2]$-set with $2r+2=\frac{m+1}{2}=\lceil \frac{m}{2}\rceil =i(C_m\square P_2)$ vertices.

Once we have proven the existence of an independent $[1,2]$-set in $C_m\square P_2$ ($m\ne 5$), with size $i(C_m\square P_2)$, the desired equality now comes from Equation (1). □

Remark 1.

It is known that $\gamma (C_m\square P_2)=\lceil \frac{m}{2}\rceil +1$ if $m\equiv 2\left(\mathrm{mod}4\right)$ and $\gamma (C_m\square P_2)=\lceil \frac{m}{2}\rceil$ if $m\equiv 3\left(\mathrm{mod}4\right)$ [11]. In these cases, no efficient dominating set exists and Proposition 3 shows that minimum independent $[1,2]$-sets play a similar role to such sets, in the sense that they provide the most efficient way of dominating these cylinders and they are at the same time minimum dominating sets.

In the same way, we obtained the value of $i_{[1,2]}$ in the case n is as small as possible, we now study the case with the smallest cycle, that is $C_3\square P_n$. Here, we also supply an example of an independent $[1,2]$-set that proves to be minimum. Henceforth, we will say that $C_m\square P_n$ has m rows and n columns. Each row is a path with n vertices and each column is a cycle with m vertices. We numerate rows from top to bottom and we numerate columns from left to right.

Proposition 4.

Let $n\ge 2$ be an integer. Then the cylinder $C_3\square P_n$ has an independent $[1,2]$-set. Moreover,

$$i_{[1,2]}(C_3\square P_n)=i(C_3\square P_n)=n.$$

Proof. 

We just need to prove that $C_3\square P_n$ has an independent $[1,2]$-set with $i(C_3\square P_n)$ elements. In Figure 3, we show a regular pattern for such a set, for any value of n. Clearly, this set has n elements, one in each column, so $i_{[1,2]}(C_3\square P_n))\le n=i(C_3\square P_n)$ (for the last equality see [14]). □

Remark 2.

We would like to point out that the value of the domination number of cylinder $C_3\square P_n$ that appears in [12], $\gamma (C_3\square P_n)=\lceil \frac{3n+1}{3}\rceil$ is not correct. The correct one is $\gamma (C_3\square P_n)=\lceil \frac{3n}{4}\rceil +1$ if $n\equiv 0\left(\mathrm{mod}4\right)$ and $\gamma (C_3\square P_n)=\lceil \frac{3n}{4}\rceil$ otherwise, and it can be found in [11]. In Figure 4a, we show a minimum dominating set of $C_3\square P_8$ with $\lceil \frac{24}{4}\rceil +1=7$ vertices and, in Figure 4b, a dominating set of $C_3\square P_9$ with $\lceil \frac{27}{4}\rceil =7$ vertices. None of them are independent sets; indeed, $\gamma (C_3\square P_n)=i(C_3\square P_n)$ if and only if $1\le n\le 4$.

Once we have studied the cases with the smallest values of m and n, we now focus on the general case. Our target is to prove that every cylinder $C_m\square P_n$, with $m\ge 4$ and $n\ge 3$ has an independent $[1,2]$-set. To this end we construct regular patterns that can be replicated in order to cover all the cases. These patterns will also provide an upper bound of $i_{[1,2]}$. We think that it could be possible to separately study some other small cases, for instance $m=4$ or $m=5$, to obtain the exact values of the independent $[1,2]$-number. However, we now prefer to provide general constructions, even if they are not minimum ones, that can be used in cylinders of any size, in order to prove the general existence of independent $[1,2]$-sets. On the other hand, we will compute the exact value of $i_{[1,2]}$ for a number of small cases in the following sections. We divide our study into two results, one for odd paths and another for even paths. We begin with the odd case.

Theorem 1.

Let $m\ge 4$ be an integer and let $n\ge 3$ be an odd integer. Then the cylinder $C_m\square P_n$ has an independent $[1,2]$-set. Moreover in this case

$$i_{[1,2]}(C_m\square P_n)\le ⌊\frac{m(n+1)}{4}⌋.$$

Proof. 

 

Case 1: $m=2r\ge 4$.

Using $n=2k+1\ge 3$, consider the pattern described in Figure 5, where set S consists of black vertices. There are no vertices of S in the even columns. Regarding odd columns, we begin with vertices in odd positions in the first one and then we alternate with vertices in even positions. Clearly S is an independent $[1,2]$-set in $C_{2r}\square P_{2k+1}$. Moreover, in each odd column there are r vertices of S, so

$$\left|S\right|=r(k+1)=\frac{m}{2}·\frac{n+1}{2}=\frac{m(n+1)}{4}=⌊\frac{m(n+1)}{4}⌋.$$

Case 2: $m=2r+1\ge 5$ and $n=4k+1\ge 5$.

Consider the pattern described in Figure 6. Here, we use a basic block with four columns, which we repeat k times, and a rest with one column.

In the basic block, vertices in S in the first column are in even positions, in the second column the unique vertex in S is the last one. In the third column, vertices in S are the ones in the odd positions, except the first and the last ones. Finally, in column number four, we pick just the first vertex. Therefore, there are $r+1+(r-1)+1=2r+1$ vertices of S in each basic block (see Figure 6).

The last column contains r vertices in S which are in even positions (see Figure 6). Clearly, S is an independent $[1,2]$-set of $C_{2r+1}\square P_{4k+1}$ and moreover,

$$\left|S\right|=(2r+1)k+r=m·\frac{n-1}{4}+\frac{m-1}{2}=\frac{m(n+1)-2}{4}=⌊\frac{m(n+1)}{4}⌋.$$

Case 3: $m=2r+1\ge 5$ and $n=4k+3\ge 3$.

We now take the pattern in Figure 7. Again, we repeat the same basic block as before k times, and we add a rest with three columns. If $k=0$ and $n=3$, we just consider the rest with three columns. In any case, the resulting set S is an independent $[1,2]$-set of $C_{2r+1}\square P_{4k+3}$. We know that a basic block contains $2r+1$ vertices of S and note that the rest contains $r+1+r$ vertices of S, therefore

$$\left|S\right|=(2r+1)k+(2r+1)=(2r+1)(k+1)=m·\frac{n+1}{4}=⌊\frac{m(n+1)}{4}⌋.\hspace{1em}\square$$

We now complete the study of the existence of independent $[1,2]$-sets in cylinders with the following theorem, covering the remaining case, that is, when n is even.

Theorem 2.

Let $m\ge 4$ be an integer and let $n\ge 4$ be an even integer. Then, the cylinder $C_m\square P_n$ has an independent $[1,2]$-set. Moreover, in this case,

$$i_{[1,2]}(C_m\square P_n)\le \left\{\begin{array}{cc}{\displaystyle ⌊\frac{m}{3}⌋n}\hfill & ifm\equiv 0,1\left(\mathrm{mod}3\right),\hfill \\ {\displaystyle ⌊\frac{m}{3}⌋n+\frac{n}{2}}\hfill & ifm\equiv 2\left(\mathrm{mod}3\right).\hfill \end{array}\right.$$

Proof. 

 

Case 1: $m=3r$.

We consider here the pattern described in Figure 8 that provides an independent $[1,2]$-set S, in $C_{3r}\square P_n$. Note that each column contains r vertices of S, so

$$\left|S\right|=rn=\frac{m}{3}n=⌊\frac{m}{3}⌋n.$$

Case 2: $m=3r+1\ge 4$.

To describe the pattern we use here, we begin with a single column. Vertices in S in such a column are those in positions a multiple of three plus one, except the vertex in position $m=3r+1$, so the column contains r vertices in S. We call the vertex in position one in the column the mark vertex, and, by construction, the mark vertex belongs to S (see Figure 9a, mark vertex with a square). We repeat this distribution of vertices in S in the second column, but rotating the cycle in such a way that the mark vertex is in the position two units smaller (modulo m) (see Figure 9b, the arrow shows rotation). The set S is an independent $[1,2]$-set in this pair of columns.

Consider now a new pair of columns with the distribution of vertices in S described above. We join it to the preceding pair, and, in this case, we rotate the cycles so that the mark vertex is in position one unit larger (modulo m) (see Figure 9c, the arrows show rotations). Again, we obtain an independent $[1,2]$-set in the resulting cylinder. Repeating this operation as many times as necessary, we obtain an independent $[1,2]$-set S in $C_{3r+1}\square P_{2k}$ (see Figure 9d, the arrows show rotations).

We show in Figure 9 an example with ten rows, but the construction also works for smaller cases (four and seven rows), and for bigger cases. Regarding the cardinality of S, note that there are r vertices of S in each column, so

$$\left|S\right|=rn=\frac{m-1}{3}n=⌊\frac{m}{3}⌋n.$$

Case 3: $m=3r+2\ge 5$.

We begin here with two types of columns. In Type A columns, vertices in S are in positions multiple of three plus one, except in position $3m+1$; in addition we include vertex in position $3m$ (see Figure 10a). We call the vertex in position one in the column the Type A mark vertex, and, by construction, this vertex belongs to S. Note that there are $r+1$ vertices of S in type A columns.

In Type B columns, vertices in S are in positions multiple of three plus one, except in position $3m+1$. We do not add any other vertex here (see Figure 10b). We call the vertex in position one in the column the Type B mark vertex, which belongs to S. In a Type B column there are r vertices in S.

Rules to join both types of columns, in order to obtain the desired independent $[1,2]$-set, are the following. We first need a four-column block, of types A, B, B and A (in this order), where each column is rotated, in reference to the previous one, until placing mark vertices as shown in Figure 10c. Note that vertices in S in this block are an independent $[1,2]$-set in the block.

We now make a two-column block by placing a Type B column and a Type A column (in this order), in such a way that mark vertices are in positions shown in Figure 10d.

We place a two-column block after another block (with four or two columns), rotating the second block in such a way that its mark vertex is in positions shown in Figure 10e,f.

The desired independent $[1,2]$-set S is obtained with one initial four-column block and attaching to it as many two-column blocks as necessary, to obtain the cylinder $C_m\square P_{2k}$ (note that $2k\ge 4$) (see Figure 11). Note that, although vertices in S in a two-column block are not a dominating set by themselves, as can be seen in Figure 10d, when we attach such a block to one four-column block following the rotation rules as described above, we obtain an independent $[1,2]$-set S (see Figure 10e). After this first operation, adding a new two-column block keeps independent $[1,2]$-domination (see Figure 11). We show in this figure the case $m=11$, but the same pattern works with smaller cases $m=5$ and $m=8$, and also with larger ones.

The four-column block contains two type A and two type B columns, so there are $2(r+1)+2r=4r+2$ vertices of S in the block. On the other hand, two-column blocks consist of one type A and one type B column, so they have $(r+1)+r=2r+1$ vertices in S. Finally, S contains one four-column block and $k-2$ two-column blocks, so:

$$\left|S\right|=(4r+2)+(2r+1)(k-2)=(2r+1)k=(2\frac{m-2}{3}+1)\frac{n}{2}=\frac{m-2}{3}n+\frac{n}{2}=⌊\frac{m}{3}⌋n+\frac{n}{2}.\hspace{1em}\square$$

3. Computing the Independent [$\mathbf{1},\mathbf{2}$]-Number in Cylinders

Having proven that every cylinder, except $C_5\square P_2$, has an independent $[1,2]$-set, in this section, we present an algorithm to compute the independent $[1,2]$-number in cylinders of small sizes. This is an adaptation of the algorithm presented in [15], to compute the domination number of grids. A modified version of this algorithm also appears in [16,17]. Although the steps of the algorithm are quite similar to the original one, we prefer to completely described it, in order to fix notation and to point out the differences. We focus on cylinders $C_m\square P_n$ with $m\ge 4$, because the case $m=3$ was solved in Proposition 4.

The main tool of the algorithm is the $(min,+)$ matrix multiplication. This is the standard matrix multiplication for the semi-ring of tropical numbers in the min convention (see [18]), that is, the usual multiplication is replaced by sum, whereas the usual sum is replaced by minimization. Therefore, the $(min,+)$ product of an $m\times n$ matrix A and an $n\times p$ matrix B is computed by the formula ${(A⊠B)}_{i,j}=\underset{1\le k\le n}{min}(a_{i,k}+b_{k,j})$. Moreover, the $(min,+)$ product of a matrix A and a scalar c is computed by ${(c⊠A)}_{i,j}=c+a_{i,j}$.

The other key point of the algorithm is the identification of columns of the cylinder with words in the alphabet $\{0,1,2,3\}$, in such a way that the number in each vertex describes its behaviour regarding independent $[1,2]$-domination. We next describe how we will do this. Let $C_m\square P_n$ be a cylinder and let $S\subseteq V(C_m\square P_n)$ be an independent $[1,2]$-set. We identify each vertex u with an element of the set $\{0,1,2,3\}$, following these rules:

• $u=0$ if $u\in S$;
• $u=1$ if u has exactly one neighbor in S in its column or in the previous one;
• $u=2$ if u has exactly two neighbors in S in its column or in the previous one;
• $u=3$ if u has no neighbors in S in its column or in the previous one.

By definition, each vertex equal to 2 has at least one neighbor in S in its column and each vertex equal to 3 has a unique neighbor in S, which is in the following column. Every vertex in the cylinder is in exactly one of the preceding situations, so all of them can be identified with a unique number. Therefore each column can be seen as a word of length m in the alphabet $\{0,1,2,3\}$, where the first and last letters are consecutive, because columns in the cylinder $C_m\square P_n$ are cycles with m vertices. The property of set S being an independent $[1,2]$-set provides a number of restrictions in words that can appear, which we list below. In all the restrictions, we consider that the first and last letters of the word P(≡ column) are consecutive, because each column is a cycle. If P is a word associated to an independent $[1,2]$-set S, then P does not contain any of the following sequences:

(a)

$00,22,33,112,211,212,213,321,1111,1113,3111,3113$

(b)

$03,30,010,121,123,321,323$

(c)

$12021,12023,32021,32023$

Note that any sequence of List (a) in a column implies that in the column, or in the previous one, or in the following one, there are two consecutive vertices of S, so it is not possible. Sequences in list (b) are not allowed because of the rules for associating each vertex with its number. Finally, sequences of list (c) do not appear in any column because each vertex has at most two neighbors in S and in all cases, such a sequence implies that in the previous column there is a vertex (next to the zero) with three neighbors in S. A word of length m in the alphabet $\{0,1,2,3\}$ not containing any of the sequences in Lists (a), (b) and (c) is called a correct word.

We also need to bear in mind that the first and last columns of the cylinder play a different role than interior ones, because they are placed next to a unique column, not between two columns. A word in the first column satisfies that every vertex equal to 1 has a neighbor in the column (just one) equal to 0, and every vertex equal to 2 has both neighbors in the column equal to 0. A correct word satisfying these conditions is called an initial word. On the other hand, the word in the last column does not contain any vertex equal to 3 and we call correct words satisfying this property final words.

Some restrictions regarding rows also arise. They can be described with rules that describe where a column P can be placed in the following position of column Q. In order to collect these restrictions, we denote letters in words P and Q as $P=p_1{p}_2\cdots p_m$ and $Q=q_1{q}_2\cdots q_m$ and in the following cases, indices are taken modulo m,

(i)

if $q_i=0$, then either $\left\{p_i=2\mathrm{and}\{p_{i-1}\ne 0\mathrm{or}{p}_{i+1}\ne 0,\mathrm{but}\mathrm{not}\mathrm{both}\mathrm{are}\mathrm{non}-\mathrm{zero}\}\right\}$ or $\left\{p_i=1\mathrm{and}{p}_{i-1}\ne 0\mathrm{and}{p}_{i+1}\ne 0\right\}$;

(ii)

if $q_i=1$, then either $p_i=0$ or $\left\{p_i=1\mathrm{and}\{p_{i-1}\ne 0\mathrm{or}{p}_{i+1}\ne 0,\mathrm{but}\mathrm{not}\mathrm{both}\mathrm{are}\mathrm{non}-\mathrm{zero}\}\right\}$ or $\left\{p_i=2\mathrm{and}{p}_{i-1}=0\mathrm{and}{p}_{i+1}=0\right\}$ or $p_i=3$;

(iii)

if $q_i=2$, then either $\left\{p_i=1\mathrm{and}\{p_{i-1}\ne 0\mathrm{or}{p}_{i+1}\ne 0,\mathrm{but}\mathrm{not}\mathrm{both}\mathrm{are}\mathrm{non}-\mathrm{zero}\}\right\}$ or $p_i=3$;

(iv)

if $q_i=3$, then $p_i=0$.

If words P and Q satisfy Conditions (i) to (iv), we say that P can follow Q. Clearly, each independent $[1,2]$-set in the cylinder $C_m\square P_n$ can be identified with a unique ordered list $P_1,P_2,\cdots ,P_n$, of n correct words of length m in the alphabet $\{0,1,2,3\}$, such that

• $P_1$ is initial;
• $P_{i+1}$ can follow $P_i$, for $i\in \{1,2,\cdots n-1\}$;
• $P_n$ is final.

We denote such ordered lists as $(m,n)$-lists. An ordered list satisfying properties 1 and 2 is called an $(m,n)$-quasilist.

To compute the independent $[1,2]$-number of $C_m\square P_n$, that is, the minimum number of zeros among all $(m,n)$-lists, we define the following vector. Denote by $c_m$ the cardinality of the set $\{P_1,P_2,\cdots ,P_{c_m}\}$ of correct words of length m. The vector $X^1=({\alpha }_1,{\alpha }_2,\cdots ,{\alpha }_{c_m})$, of length $c_m$, is defined as follows:

$${\alpha }_i=\left\{\begin{array}{cc}\mathrm{number}\mathrm{of}\mathrm{zeros}\mathrm{of}{P}_i\hfill & \mathrm{if}{P}_i\mathrm{is}\mathrm{initial},\hfill \\ +\infty \hfill & \mathrm{otherwise}.\hfill \end{array}\right.$$

We also define the matrix $A_{c_m\times c_m}=\left(a_{i,j}\right)$, a square matrix of size $c_m$ such that

$$a_{i,j}=\left\{\begin{array}{cc}\mathrm{number}\mathrm{of}\mathrm{zeros}\mathrm{of}{P}_i\hfill & \mathrm{if}{P}_i\mathrm{can}\mathrm{follow}{P}_j,\hfill \\ +\infty \hfill & \mathrm{otherwise}.\hfill \end{array}\right.$$

By multiplying vector $X^1$ and matrix A, with the $(min,+)$ matrix multiplication, we obtain a new vector $X^2=A⊠X^1=({\beta }_1,{\beta }_2,\cdots ,{\beta }_{c_m})$, and, clearly, every finite entry

$${\beta }_i=\underset{1\le j\le c_m}{min}({\alpha }_j+a_{i,j})<+\infty$$

represents the minimum number of zeros among all $(m,2)$-quasilists having $P_i$ as its second word. We can repeat this process as many times as we need, so if $X^n=A⊠X^{(n-1)}=({\delta }_1,{\delta }_2,\cdots ,{\delta }_{c_m})$, then every finite entry ${\delta }_i<+\infty$, represents the minimum number of zeros among all $(m,n)$-quasilists having $P_i$ as its last word. Having in mind that an $(m,n)$-quasilist whose last word is final is an $(m,n)$-list, we obtain

$$i_{[1,2]}(C_m\square P_n)=min\{{\delta }_i:P_i\mathrm{is}\mathrm{a}\mathrm{final}\mathrm{word}\}.$$

(2)

Moreover, algebraic properties of $(min,+)$ matrix multiplication give the following result, which is similar to Theorem 2.2 of [16].

Proposition 5.

Let $m\ge 3$ be an integer and suppose that there exist $n_0,c,d>0$ such that $X^{n_0+d}=c⊠X^{n_0}$. Then $X^{n+d}=c⊠X^n$ for every $n\ge n_0$, and moreover

$$i_{[1,2]}(C_m\square P_{n+d})=i_{[1,2]}(C_m\square P_n)+c.$$

Proof. 

We prove by induction that $X^{n+d}=c⊠X^n$ for every $n\ge n_0$. On the one hand, $X^{n_0+d}=c⊠X^{n_0}$ by hypothesis. Assume now that $X^{(n-1)+d}=c⊠X^{(n-1)}$ for $n-1\ge n_0$. Then, properties of the $(min,+)$ matrix algebra and the inductive hypothesis give

$$X^{n+d}=A⊠X^{(n-1)+d}=A⊠(c⊠X^{(n-1)})=c⊠(A⊠X^{(n-1)})=c⊠X^n.$$

Therefore, if $X^{n+d}=({ϵ}_1,{ϵ}_2,\cdots ,{ϵ}_{c_m})$ and $X^n=({\delta }_1,{\delta }_2,\cdots ,{\delta }_{c_m})$, then ${ϵ}_i={\delta }_i+c$ for every index i. In particular, ${ϵ}_i$ is finite if and only if ${\delta }_i$ is finite. Finally this gives

$$\begin{array}{cc}{i}_{[1,2]}(C_m\square P_{n+d})\hfill & =min\{{ϵ}_i:P_i\mathrm{is}\mathrm{a}\mathrm{final}\mathrm{word}\}\hfill \\ & =min\{{\delta }_i+c:P_i\mathrm{is}\mathrm{a}\mathrm{final}\mathrm{word}\}\hfill \\ & =min\{{\delta }_i:P_i\mathrm{is}\mathrm{a}\mathrm{final}\mathrm{word}\}+c\hfill \\ & =i_{[1,2]}(C_m\square P_n)+c.\square \hfill \end{array}$$

Results presented in this section provide the following algorithm to compute the independent $[1,2]$-number of $C_m\square P_n$. It is an adaptation of the algorithm presented in [15], to compute the domination number of grids. A modified version of this algorithm also appears in [16,17]. On the one hand, the algorithm computes the value of $i_{[1,2]}(C_m\square P_n)$ for fixed and small enough $(m,n)$. On the other hand, given a fixed m, it computes a list of vectors $X^1,X^2,\cdots ,X^r$ and it tries to find the recurrence relationship on the hypothesis of Proposition 5.

If a recurrence is found by Algorithm 1, Proposition 5 provides a finite difference equation

$$i_{[1,2]}(C_m\square P_{n+d})-i_{[1,2]}(C_m\square P_n)=c,\mathrm{for}n\ge n_0.$$

with d boundary values $i_{[1,2]}(C_m\square P_s),\mathrm{for}{n}_0\le s\le n_0+d-1$. The solution of this equation is

$$i_{[1,2]}(C_m\square P_n)=⌈\frac{cn+\beta }{d}⌉,\mathrm{for}n\ge n_0,$$

where the value of $\beta$ depends on the boundary values. Remaining values of $i_{[1,2]}(C_m\square P_n)$, that is for $2\le n\le n_0-1$, have also been computed by the algorithm, so finding the recurrence means that the independent $[1,2]$-number of $C_m\square P_n$ is completely computed.

Algorithm 1: Recurrence for the Independent $[1,2]$-number in Cylinders

However, the existence of such a recurrence relationship is not guaranteed, as was mentioned in Section 6 of [15]. Some sufficient conditions on an arbitrary matrix A, in the $(min,+)$ matrix algebra, are known that ensure such a recurrence exists. We recall the following definition from [15]. A matrix A is irreducible if there exists an integer K such that for every $k\ge K$, matrix $A^k$ has no infinite entries, and this is analogous to the definition of irreducible matrix in regular matrix algebra. Theorem 6.3 of [15] states that, if A is an irreducible matrix, then the recurrence needed to apply Proposition 5 occurs.

The following characterization is well known; see, for instance, [19]. Considering matrix A as the adjacency matrix of a directed graph (there is an arc from j to i if and only if $a_{i,j}<+\infty$), A is irreducible if and only if such a directed graph is strongly connected. In particular, a matrix such that every entry in the $i^{th}$ row is equal to $+\infty$ is not irreducible, because no arc arrives to i. When this situation happens, the recurrence needed in Proposition 5 could not occur.

This is the main difference between the computation of the independent $[1,2]$-number in cylinders and the previous cases where this algorithm has been used (see [15,16,17]). In our case, matrices defined using the properties of independent $[1,2]$-sets have an increasing number of rows with no finite entry, when m gets larger. In fact, we just found the desired recurrence in cases $m=4$ and $m=5$. If $m\ge 6$ our strategy consists of modifying the first step of the algorithm. We consider a reduced collection $\mathcal{C}$ of correct words instead of having all of them, so we obtain an auxiliary parameter $f_m\left(n\right)$ that represents the minimum number of zeros among all $(m,n)$-lists with words in $\mathcal{C}$, if there exists at least one of such $(m,n)$-list. Then, we use the algorithm to look for the recurrence relationship, but using just correct words in subset $\mathcal{C}$ and, in the case it is found, the auxiliary function obtained satisfies $i_{[1,2]}(C_m\square P_n)\le f_m\left(n\right)$. The final step consists of combining this upper bound with an appropriate lower bound, in order to localize the independent $[1,2]$-number in an interval as small as possible.

4. Experimental Results

In this section, we present the results obtained with Algorithm 1, for values of m between 4 and 15. The link to the source code, in programming language C, to perform all the operations described in the algorithm can be found in the Supplementary Materials. Notice that vector $X^1$ is computed using its definition, but vectors $X^2,X^3,\cdots ,X^r$ are obtained by successively multiplying matrix A and vector $X^1$, with the $(min,+)$ matrix multiplication. We do this operation by means of an adaptation of the CSPARSE library [20]. This library provides a fast method for multiplying sparse matrices with the usual product, and we have adapted it for the $(min,+)$ matrix product. Therefore, we have obtained a library that efficiently multiplies sparse matrices, also with this product, as can be seen in

Table 1. Execution times with only one core, Intel(R) Core(TM) i7-3632QM at 2.20 GHz processor.

m	$4^{\mathit{m}}=$ Words of Length m in Alphabet $\{0,1,2,3\}$	${\mathit{c}}_{\mathit{m}}=$ Number of Correct Words	Execution Times
			Correct Words	A	${\mathit{X}}^{\mathit{r}}$, $2\le \mathit{r}\le 100$
4	256	20	$<1$ s.	$<1$ s.	$<1$ s.
5	1024	35	$<1$ s.	$<1$ s.	$<1$ s.
6	4096	79	$<1$ s.	$<1$ s.	$<1$ s.
7	16384	154	$<1$ s.	$<1$ s.	$<1$ s.
8	65536	332	$<1$ s.	$<1$ s.	$<1$ s.
9	262144	666	$<1$ s.	$<1$ s.	$<1$ s.
10	1048576	1389	$<1$ s.	$<1$ s.	$<1$ s.
11	4194304	2849	$<1$ s.	$2.6$ s.	$<1$ s.
12	16777216	5891	$2.2$ s.	$11.8$ s.	$1.9$ s.
13	67108864	12116	$8.1$ s.	$53.2$ s.	$3.7$ s.
14	268435456	25008	$31.1$ s.	4 m. 3 s.	$6.9$ s.
15	1073741824	51509	2 m. 5 s.	18 m. 25 s.	$13.3$ s.

, where we show that execution times for computing the first 100 vectors are shorter than times for the computation of the matrix. We have also included computation times for the set of correct words, but not for vector $X^1$, because it is less that one second in all cases.

4.1. Cases $m=$ 4 and $m=$ 5

In both cases, we have found the recurrence needed to apply Proposition 5, and we have completely computed the independent $[1,2]$-number of cylinders $C_m\square P_n$, for $n\ge 2$. Data obtained with Algorithm 1 and finite difference equations appear in

Table 2. Recurrence values for reduced sets of correct words.

m	${\mathit{n}}_0$	d	c	Finite Difference Equation	Boundary Values	Rest of Values
4	3	2	2	$i_{[1,2]}(C_4\square P_{n+2})-i_{[1,2]}(C_4\square P_n)=2,n\ge 3$	$i_{[1,2]}(C_4\square P_3)=3$ $i_{[1,2]}(C_4\square P_4)=4$	$i_{[1,2]}(C_4\square P_2)=2$
5	4	1	1	$i_{[1,2]}(C_5\square P_{n+1})-i_{[1,2]}(C_5\square P_n)=1,n\ge 4$	$i_{[1,2]}(C_5\square P_4)=6$	$i_{[1,2]}(C_5\square P_3)=5$

.

The solution of the finite difference equation gives the formula of the independent $[1,2]$-number. In both cases, the independent $[1,2]$-number agrees with the domination number (see [12]); therefore, independent $[1,2]$-sets provide the most efficient way to dominate these cylinders.

$$i_{[1,2]}(C_4\square P_n)=n,\mathrm{for}n\ge 2$$

$$i_{[1,2]}(C_5\square P_n)=n+2,\mathrm{for}n\ge 3.$$

4.2. Cases 6 $\le m\le$ 10

In these cases, matrices obtained with the algorithm have a large number of rows with all entries equal to $+\infty$, so they are not irreducible. This means the recurrence is not guaranteed and, in fact, we have not found it in the first 100 vectors. Clearly, it could happen that the recurrence relationship exists for some $n_0\ge 100$, but instead of keeping on looking for a recurrence in larger values, we prefer a different approach.

We remove a group of correct words and we use Algorithm 1 again, but considering the remaining word subset instead of the complete list of correct words computed in step 1. The criterion for removing words takes into account formulas for the independent domination number $i(C_m\square P_n)=\lceil \frac{cn+\beta }{d}\rceil$ obtained in [14], and we look for similar formulas for the independent $[1,2]$-number. We fixed vector $X^{20}$ because it is small enough to quickly use the algorithm and it gives positive results in cases we are considering. For each m, we take the integer d in formula $i(C_m\square P_n)=\lceil \frac{cn+\beta }{d}\rceil$ and we study the pair of vectors $X^{20},X^{20+d}$. Their entries in the $i^{th}$ position, $X^{20}\left(i\right),X^{20+d}\left(i\right)$, are in one of the following situations:

• both are infinite;
• both are finite, then we compute the difference $X^{20+d}\left(i\right)-X^{20}\left(i\right)$;
• one of them is finite and the other one is infinite, then we say that they are non-comparable.

If a recurrence is not found, then either there are non-comparable pairs or differences of finite entries are not equal, or both. In

Table 3. Criteria for removing some correct words.

m	d	c	Vector Pair ${\mathit{X}}^{20+\mathit{d}},{\mathit{X}}^{20}$	Values of Differences	Non-Comparable Pairs	Remove Correct Words in Positions Where Appears	Remaining Words
6	3	4	$X^{23},X^{20}$	$4,6$	yes	6, non-comparable	69
7	2	3	$X^{22},X^{20}$	$3,4$	no	4	126
8	5	9	$X^{25},X^{20}$	$9,10$	yes	10, non-comparable	228
9	2	4	$X^{22},X^{20}$	$4,6$	no	6	660
10-I	2	4	$X^{22},X^{20}$	$2,4,5,6$	no	$2,5,6$	1077
10-II	2	4	$X^{22},X^{20}$	$4,5$	no	5	1067

, we show values of differences found and if there are non-comparable words. Recall that, for each m, the set of correct words $\{P_1,P_2,\cdots ,P_{c_m}\}$ is ordered and it has $c_m$ elements, and the size of vector $X^n$ is $c_m$. We now take the integer c in $i(C_m\square P_n)=\lceil \frac{cn+\beta }{d}\rceil$ and we keep the word in position i if both $i^{th}$ entries are finite with $X^{20+d}\left(i\right)-X^{20}\left(i\right)=c$ and also in case $X^{20+d}\left(i\right)=X^{20}\left(i\right)=+\infty$. However, we remove the word in position i if entries are finite with $X^{20+d}\left(i\right)-X^{20}\left(i\right)\ne c$ or $X^{20+d}\left(i\right),X^{20}\left(i\right)$ are non-comparable. This strategy provides a subset $\mathcal{C}$ of correct words that we use in the algorithm, instead of the complete list originally computed in the first step. In cases $6\le m\le 9$, we found the recurrence, as we expected. However, in case $m=10$, after a first selection of words, recurrence does not appear and we remove a second group of words, with the same criterion. It is shown in Table 3, in rows 10-I and 10-II. After removing the second word group, a recurrence also appears for $m=10$.

We now apply Algorithm 1, but using the subset $\mathcal{C}$ of remaining words instead of the complete list. We would like to point out that there exists an $(m,n)$-list with words in $\mathcal{C}$ if and only if the value of $f_m\left(n\right)=min\{{\delta }_i:P_i\in \mathcal{C}\mathrm{is}\mathrm{a}\mathrm{final}\mathrm{word}\}$ is finite, where $X^n=A^n⊠X^1=({\delta }_1,\cdots ,{\delta }_k)$, $X^1$ is the initial vector, A is the matrix, both associated to subset $\mathcal{C}$ of correct words of length m, and $\left|\mathcal{C}\right|=k$. Clearly, if this auxiliary function $f_m\left(n\right)$ is finite, then it provides the minimum number of zeros among all $(m,n)$-lists with words in $\mathcal{C}$, so it is trivially true that $i_{[1,2]}(C_m\square P_n)\le f_m\left(n\right)$. Moreover, if we just consider words in $\mathcal{C}$ and the recurrence relationships described in Proposition 5 occurs, then the finitude of boundary values ensures that $f_m\left(n\right)$ is finite, for every $n\ge n_0$.

Recurrences and boundary values found by Algorithm 1, when we just use the subset $\mathcal{C}$ of correct words described in Table 3, are shown in

Table 4. Recurrence values for reduced sets of correct words.

m	${\mathit{n}}_0$	d	c	Auxiliary Equation	Boundary Values
6	7	3	4	$f_6(n+3)-f_6\left(n\right)=4,n\ge 7$	$f_6\left(7\right)=10,f_6\left(8\right)=12,f_6\left(9\right)=13$
7	6	2	3	$f_7(n+2)-f_7\left(n\right)=3,n\ge 6$	$f_7\left(6\right)=12,f_7\left(7\right)=13$
8	11	5	9	$f_8(n+5)-f_8\left(n\right)=9,n\ge 11$	$f_8\left(11\right)=21,f_8\left(12\right)=24,f_8\left(13\right)=25$ $f_8\left(14\right)=28,f_8\left(15\right)=29$
9	8	2	4	$f_9(n+2)-f_9\left(n\right)=4,n\ge 8$	$f_9\left(8\right)=18,f_9\left(9\right)=20$
10	10	2	4	$f_{10}(n+2)-f_{10}\left(n\right)=4,n\ge 10$	$f_{10}\left(10\right)=24,f_{10}\left(11\right)=26$

.

The solutions of auxiliary equations are the following:

$\begin{array}{cc}m=6,n\ge 7:\hfill & f_6\left(n\right)=\left\{\begin{array}{cc}⌈\frac{4n}{3}⌉\hfill & \mathrm{if}n\equiv 1\left(\mathrm{mod}3\right),\hfill \\ ⌈\frac{4n}{3}⌉+1\hfill & \mathrm{otherwise}.\hfill \end{array}\right.\hfill \\ m=7,n\ge 5:\hfill & f_7\left(n\right)=\left\{\begin{array}{cc}⌈\frac{3n}{2}⌉+2\hfill & \mathrm{if}n\equiv 1\left(\mathrm{mod}2\right),\hfill \\ ⌈\frac{3n}{2}⌉+3\hfill & \mathrm{otherwise}.\hfill \end{array}\right.\hfill \\ m=8,n\ge 11:\hfill & f_8\left(n\right)=\left\{\begin{array}{cc}⌈\frac{9n}{5}⌉+1\hfill & \mathrm{if}n\equiv 1,3\left(\mathrm{mod}5\right),\hfill \\ ⌈\frac{9n}{5}⌉+2\hfill & \mathrm{if}n\equiv 0,2,4\left(\mathrm{mod}5\right).\hfill \end{array}\right.\hfill \\ m=9,n\ge 8:\hfill & f_9\left(n\right)=2n+2.\hfill \\ m=10,n\ge 10:\hfill & f_{10}\left(n\right)=2n+4.\hfill \end{array}$

As we mentioned before, $f_m\left(n\right)$ is an upper bound of the independent $[1,2]$-number of $C_m\square P_n$, and we now combine these results with the values of $i(C_m\square P_n)$ [14], which is a natural lower bound, that is

$$i(C_m\square P_n)\le i_{[1,2]}(C_m\square P_n)\le f_m\left(n\right).$$

In cases $m=6,7,9,10$ and also in case $m=8,n\equiv 0,1,3\left(\mathrm{mod}5\right)$, we obtained $f_m\left(n\right)=i(C_m\square P_n)$, so the independent $[1,2]$-number agrees with the independent domination number. In case $m=8$ and $n\ge 12,n\equiv 2,4\left(\mathrm{mod}5\right)$, we obtained $f_m\left(n\right)=i(C_m\square P_n)+1$; the bounds do not agree and we can just conclude that $i(C_m\square P_n)\le i_{[1,2]}(C_m\square P_n)\le i(C_m\square P_n)+1$. We computed the independent $[1,2]$-number for $12\le n\le 100,n\equiv 2,4\left(\mathrm{mod}5\right)$ and it agrees with the upper bound in all cases.

We also computed the independent $[1,2]$-number of small cylinders ($n\le n_0-1$) with the algorithm, by using Equation (2) with the complete list of correct words. We include these values in the final formulas.

• $i_{[1,2]}(C_6\square P_n)=\left\{\begin{array}{cc}6\hfill & \mathrm{if}n=3,\hfill \\ 9\hfill & \mathrm{if}n=5,\hfill \\ ⌈\frac{4n}{3}⌉\hfill & \mathrm{if}n\equiv 1\left(\mathrm{mod}3\right),\hfill \\ ⌈\frac{4n}{3}⌉+1\hfill & \mathrm{otherwise}.\hfill \end{array}\right.$
• $i_{[1,2]}(C_7\square P_n)=\left\{\begin{array}{cc}2n\hfill & \mathrm{if}n=2,3,4,\hfill \\ ⌈\frac{3n}{2}⌉+2\hfill & \mathrm{if}n\equiv 1\left(\mathrm{mod}2\right),\hfill \\ ⌈\frac{3n}{2}⌉+3\hfill & \mathrm{otherwise}.\hfill \end{array}\right.$
• $i_{[1,2]}(C_8\square P_n)=\left\{\begin{array}{cc}2n\hfill & \mathrm{if}n=2,3,4,5,7,9,\hfill \\ ⌈\frac{9n}{5}⌉+1\hfill & \mathrm{if}n\equiv 1,3\left(\mathrm{mod}5\right),\hfill \\ ⌈\frac{9n}{5}⌉+2\hfill & \mathrm{if}n\equiv 0\left(\mathrm{mod}5\right)\mathrm{or}n\le 100,n\equiv 2,4\left(\mathrm{mod}5\right).\hfill \end{array}\right.$
• $⌈\frac{9n}{5}⌉+1\le i_{[1,2]}(C_8\square P_n)\le ⌈\frac{9n}{5}⌉+2$, if $n>100$ and $n\equiv 2,4\left(\mathrm{mod}5\right).$
• $i_{[1,2]}(C_9\square P_n)=2n+2$, if $n\ge 2$.
• $i_{[1,2]}(C_{10}\square P_n)=\left\{\begin{array}{cc}2n+2\hfill & \mathrm{if}n=2,4,5,\hfill \\ 2n+3\hfill & \mathrm{if}n=3,6,7,8,9,\hfill \\ 2n+4\hfill & \mathrm{otherwise}.\hfill \end{array}\right.$

4.3. Cases 11 $\le m\le$ 15

In these cases, the independent domination number is not known, so our first task is to compute it. We will use these values as a lower bound of the independent $[1,2]$-number. To this end we have implemented the algorithm described in [16], to compute the independent domination number of the grid $P_m\square P_n$, making the necessary changes to adapt it to the cylinder $C_m\square P_n$. These changes just consist of considering that the first and the last letters in each word are neighbors. Computations can be done following the same steps as in Algorithm 1, but taking into account the rules to define correct words and to compute vector $X^1$ and matrix A that correspond with the definition of independent domination. For the sake of completeness, we recall these rules from [16]. For an independent dominating set S of $C_m\square P_n$, each vertex $u\in V(C_m\square P_n)$ is identified with an element of the set $\{0,1,2\}$, following these rules:

• $u=0$ if $u\in S$;
• $u=1$ if u has at least one neighbor in S, in its column or in the previous one;
• $u=2$ if u has no neighbors in S, in its column or in the previous one.

Each column in $C_m\square P_n$ can be seen as a word of length m in the alphabet $\{0,1,2\}$, where the first and last letters are consecutive. Correct words are those words not containing the sequences $00,22,1111,1112,2111,2112$. For a pair of correct words $P,Q$, we say that $P=p_1{p}_2\cdots p_m$ can follow $Q=q_1{q}_2\cdots q_m$ if they satisfy the following conditions

(i)

if $q_i=0$, then $p_i=1$,

(ii)

if $q_i=1$, then either $p_i=0$ or $\left\{p_i=1\mathrm{and}\{p_{i-1}\ne 0\mathrm{or}{p}_{i+1}\ne 0,\}\right\}$ or $p_i=2$,

(iii)

if $q_i=2$, then $p_i=0$.

Following the same steps as in Algorithm 1 with the rules described above, recurrence is found for $11\le m\le 15$ and we present the final formulas obtained (we have not included small cases not following the general formula).

$\begin{array}{cc}i(C_{11}\square P_n)=⌈\frac{12n+12}{5}⌉\hfill & \mathrm{if}n\ge 4.\hfill \\ i(C_{12}\square P_n)=⌈\frac{5n+9}{2}⌉\hfill & \mathrm{if}n\ge 17.\hfill \\ i(C_{13}\square P_n)=⌈\frac{20n+20}{7}⌉\hfill & \mathrm{if}n\ge 6.\hfill \\ i(C_{14}\square P_n)=3n+4\hfill & \mathrm{if}n\ge 12.\hfill \\ i(C_{15}\square P_n)=3n+6\hfill & \mathrm{if}n\ge 8.\hfill \end{array}$

We now follow the same strategy as in the preceding cases and we use vectors $X^{50},X^{50+d}$ because they provide positive results in all cases. For $m=11,12,13,15$, the first reduction of the correct words gives positive results and we found the recurrence. However, in case $m=14$, after a first selection of words, a recurrence does not appear and we remove a second group of words, with the same criterion. After removing the second word group, a recurrence also appears in this case. We show the rules for reducing the correct word set in

Table 5. Criteria for removing some correct words.

m	d	c	Vector Pair ${\mathit{X}}^{50+\mathit{d}},{\mathit{X}}^{50}$	Values of Differences	Non-Comparable Pairs	Remove Correct Words in Positions Where Appears	Remaining Words
11	5	12	$X^{55},X^{50}$	$11,12,13,14,15$	no	$11,13,14,15$	2475
12	2	5	$X^{52},X^{50}$	$2,4,5,6,8$	no	$2,4,6,8$	3531
13	7	20	$X^{57},X^{50}$	$19,20,21,22,23,28$	no	$19,21,22,23,28$	9438
14-I	2	6	$X^{52},X^{50}$	$2,4,5,6,7,8$	no	$2,4,5,7,8$	20792
14-II	2	6	$X^{52},X^{50}$	$6,7$	no	7	19686
15	1	3	$X^{51},X^{50}$	$1,2,3,4,5,6$	no	$1,2,4,5,6$	34913

. In

Table 6. Recurrence values for reduced sets of correct words.

m	${\mathit{n}}_0$	d	c	Auxiliary Equation	Boundary Values
11	7	5	12	$f_{11}(n+5)-f_{11}\left(n\right)=12,n\ge 7$	$f_{11}\left(7\right)=20,f_{11}\left(8\right)=22,f_{11}\left(9\right)=24$, $f_{11}\left(10\right)=27,f_{11}\left(11\right)=29$
12	8	2	5	$f_{12}(n+2)-f_{12}\left(n\right)=5,n\ge 8$	$f_{12}\left(8\right)=25,f_{12}\left(9\right)=27$
13	10	7	20	$f_{13}(n+7)-f_{13}\left(n\right)=20,n\ge 10$	$f_{13}\left(10\right)=32,f_{13}\left(11\right)=35,f_{13}\left(12\right)=38$, $f_{13}\left(13\right)=40,f_{13}\left(14\right)=44,f_{13}\left(15\right)=46,f_{13}\left(16\right)=50$
14	10	2	6	$f_{14}(n+2)-f_{14}\left(n\right)=6,n\ge 10$	$f_{14}\left(10\right)=34,f_{14}\left(11\right)=37$
15	10	1	3	$f_{15}(n+1)-f_{15}\left(n\right)=3,n\ge 10$	$f_{15}\left(10\right)=36$

, we show recurrences and finite difference equations in each case.

Solutions of auxiliary equations are the following

$\begin{array}{cccc}m=11,n\ge 7:\hfill & f_{11}\left(n\right)=⌈\frac{12n+12}{5}⌉\hfill & m=14,n\ge 10:\hfill & f_{14}\left(n\right)=3n+4\hfill \\ m=12,n\ge 8:\hfill & f_{12}\left(n\right)=⌈\frac{5n+9}{2}⌉\hfill & m=15,n\ge 15:\hfill & f_{15}\left(n\right)=3n+6\hfill \\ m=13,n\ge 10:\hfill & f_{13}\left(n\right)=\left\{\begin{array}{cc}⌈\frac{20n+20}{7}⌉+1\hfill & \mathrm{if}n\equiv 0,2\left(\mathrm{mod}7\right),\hfill \\ ⌈\frac{20n+20}{7}⌉\hfill & \mathrm{otherwise}.\hfill \end{array}\right.\hfill \end{array}$

Final formulas have been obtained by comparing auxiliary equations with the above computed independent domination number and by using inequalities $i(C_m\square P_n)\le i_{[1,2]}(C_m\square P_n)\le f_m\left(n\right)$. We also include values for small cylinders, with $n\le n_0-1$. In the case $m=13$, we also include values of $i_{[1,2]}(C_{13}\square P_n)$ for $n\le 100,n\equiv 0,2\left(\mathrm{mod}7\right)$.

• $i_{[1,2]}(C_{11}\square P_n)=\left\{\begin{array}{cc}6\hfill & \mathrm{if}n=2,\hfill \\ 9\hfill & \mathrm{if}n=3,\hfill \\ ⌈\frac{12n+12}{5}⌉\hfill & \mathrm{otherwise}.\hfill \end{array}\right.$
• $i_{[1,2]}(C_{12}\square P_n)=\left\{\begin{array}{cc}3n\hfill & \mathrm{if}n=2,3,4,\hfill \\ ⌈\frac{5n+5}{2}⌉\hfill & \mathrm{if}n=5,6,7,\hfill \\ ⌈\frac{5n+9}{2}⌉\hfill & \mathrm{if}n\ge 8.\hfill \end{array}\right.$
• $i_{[1,2]}(C_{13}\square P_n)=\left\{\begin{array}{cc}7\hfill & \mathrm{if}n=2,\hfill \\ 10\hfill & \mathrm{if}n=3,\hfill \\ ⌈\frac{20n+11}{7}⌉\hfill & \mathrm{if}4\le n\le 9,\hfill \\ ⌈\frac{20n+20}{7}⌉\hfill & \mathrm{if}n\ge 10,n\neg \equiv 0,2\left(\mathrm{mod}7\right)\mathrm{or}n=14,16,\hfill \\ ⌈\frac{20n+20}{7}⌉+1\hfill & \mathrm{if}21\le n\le 100,n\equiv 0,2\left(\mathrm{mod}7\right).\hfill \end{array}\right.$
• $⌈\frac{20n+20}{7}⌉\le i_{[1,2]}(C_{13}\square P_n)\le ⌈\frac{20n+20}{7}⌉+1$, if $n>100$ and $n\equiv 0,2\left(\mathrm{mod}7\right).$
• $i_{[1,2]}(C_{14}\square P_n)=\left\{\begin{array}{cc}8\hfill & \mathrm{if}n=2,\hfill \\ 3n+3\hfill & \mathrm{if}3\le n\le 9,\hfill \\ 3n+4\hfill & \mathrm{if}\mathrm{otherwise}.\hfill \end{array}\right.$
• $i_{[1,2]}(C_{15}\square P_n)=\left\{\begin{array}{cc}8\hfill & \mathrm{if}n=2,\hfill \\ 12\hfill & \mathrm{if}n=3,\hfill \\ 3n+4\hfill & \mathrm{if}n=4,5,\hfill \\ 3n+5\hfill & \mathrm{if}n=6,7,\hfill \\ 3n+6\hfill & \mathrm{otherwise}.\hfill \end{array}\right.$

5. Conclusions

In this paper, we have deeply studied independent $[1,2]$-sets and their associated parameter, the independent $[1,2]$-number, in cylindrical networks. The main interest of this study lies in the known fact that the cylinder $C_m\square P_n$ has an efficient dominating set if and only if $m\equiv 0\left(\mathrm{mod}4\right)$ and $n=2$, so in other cylinders different domination-like sets are needed to dominate them as efficiently as possible. On the other hand, the symmetry of these graphs allows us to focus their study from different points of view.

In Section 2, we have proven that every cylinder $C_m\square P_n$ with $(m,n)\ne (5,2)$ has an independent $[1,2]$-set. We also provided exact values of $i_{[1,2]}(C_m\square P_2),m\ne 5$ and $i_{[1,2]}(C_3\square P_n),n\ge 2$ and upper bounds for the independent $[1,2]$-number in the rest of the cases.

In Section 3, we presented an adaptation of a known algorithm to compute exact values of $i_{[1,2]}(C_m\square P_n)$; and we presented the experimental results obtained with the algorithm in Section 4, for $4\le m\le 15$. To this end, we have adapted the CSPARSE library, a fast method for multiplying sparse matrices, to the case of $(min,+)$ multiplication and we have introduced the technique of selecting some correct words when using the algorithm, providing new possibilities of applying this type of recursive computing in cases where the matrix is not irreducible and a recurrence is not found.

Regarding the cases in which we have exactly computed the independent $[1,2]$-number, comparing our results with the values of the domination number [11,12] and leaving aside the small values of n not following the general formula, we may conclude that:

• if $m=3,4,5,6,9,10,15$, then $i_{[1,2]}(C_m\square P_n)=\gamma (C_m\square P_n)$;
• if $m=7,14$, then $i_{[1,2]}(C_m\square P_n)=\gamma (C_m\square P_n)+1$;
• if $m=8,12$, then $\gamma (C_m\square P_n)\le i_{[1,2]}(C_m\square P_n)\le \gamma (C_m\square P_n)+1$,
• $i_{[1,2]}(C_{11}\square P_n)=i(C_{11}\square P_n)$;
• $i(C_{13}\square P_n)\le i_{[1,2]}(C_{13}\square P_n)\le i(C_{13}\square P_n)+1$.

Summing up, it is known that, in general, the independent $[1,2]$-number does not equal the domination number; however, we have seen that there are some cylinders having this property and some others where both parameters differ by 1. In view of these results, we may conclude that independent $[1,2]$-sets provide an interesting alternative to efficient dominating sets in cylindrical networks.