A New Lower Bound for the Domination Number of Complete Cylindrical Grid Graphs

Guichard, David

doi:10.61091/jcmcc120-38

Abstract

References

Journal of Combinatorial Mathematics and Combinatorial Computing

Volume 120
Pages: 411-416

Research article

A New Lower Bound for the Domination Number of Complete Cylindrical Grid Graphs

^¹

¹Whitman College, WA 99362, United States.

Received: 10/12/2019
Accepted: 20/12/2020
Published: 30/06/2024

Copyright Link
License

Abstract

We use a dynamic programming algorithm to establish a lower bound on the domination number of complete grid graphs of the form $C_{n} P_{m}$ , that is, the Cartesian product of a cycle $C_{n}$ and a path $P_{m}$ , for $m$ and $n$ sufficiently large.

Keywords: cylindrical grid graph, domination number

1. Introduction

A set $S$ of vertices in a graph $G = (V, E)$ is called a dominating set if every vertex $v \in V$ is either in $S$ or adjacent to a vertex in $S$ . The domination number of $G$ , $γ (G)$ , is the minimum size of a dominating set.

Let $P_{m}$ denote the path on $m$ vertices and $C_{n}$ the cycle on $n$ vertices; the complete cylindrical grid graph or cylinder is the product $C_{n} P_{m}$ . That is, if we denote the vertices of $C_{n}$ by $u_{1}, u_{2}, \dots, u_{n}$ and the vertices of $P_{m}$ by $w_{1}, \dots, w_{m}$ , then $C_{n} P_{m}$ is the graph with vertices $v_{i, j}$ , $1 \leq i \leq n$ , $1 \leq j \leq m$ , and $v_{i, j}$ adjacent to $v_{k, l}$ if $i = k$ and $w_{j}$ is adjacent to $w_{l}$ or if $j = l$ and $u_{i}$ is adjacent to $u_{k}$ . It will be useful to think of this graph as $P_{n} P_{m}$ , with the edge paths of length $m$ glued together, that is, connected with new edges.

P. Pavlič and J. Žerovnik[1] established upper bounds for the domination number of $C_{n} P_{m}$ , and José Juan Carreño et al.[2] established non-trivial lower bounds. For $n \equiv 0 (\mod 5)$ the bounds agree, so the domination number is known exactly. Here we improve the lower bounds, except of course in the case that $n \equiv 0 (\mod 5)$ . The method is similar, based on a technique first used in Guichard[3], and later in Gonçalves, et al.[4], but we use a different programming technique than that of [2].

2. Getting a Lower Bound

A vertex in $C_{n} P_{m}$ dominates at most five vertices, including itself, so certainly $γ (C_{n} P_{m}) \geq n m / 5$ . If we could keep the sets dominated by individual vertices from overlapping, we could get a dominating set with approximately $n m / 5$ vertices, and indeed we can arrange this for much of the graph, with the exception of the the top and bottom copies of $C_{n}$ in which the vertices have only 3 neighbors, and, except when $n \equiv 0 (\mod 5)$ , in the leftmost and rightmost columns of $P_{n} P_{m}$ where each vertex in the leftmost column is adjacent to the corresponding vertex in the rightmost column. Figure 1 shows one of the nice examples, when $n$ is divisible by 5.

Figure 1: The Cylinder $C_{10} P_{12}$ has Domination Number 28. (Vertices on the Right Side Are Adjacent to the Corresponding Vertices on the Left Side)

Suppose $S$ is a subset of the vertices of $C_{n} P_{m}$ . Let $N [S]$ be the set of vertices that are either in $S$ or adjacent to a member of $S$ , that is, the vertices dominated by $S$ . Define the wasted domination of $S$ as $w (S) = 5 | S | - | N [S] |$ , that is, the number of vertices we could dominate with $| S |$ vertices in the best case, less the number actually dominated. When $S$ is a dominating set, $| N [S] | = m n$ , and if $w (S) \geq L$ then $| S | \geq (L + m n) / 5$ . Our goal now is to find a lower bound $L$ for $w (S)$ .

Suppose a cylinder $C_{n} P_{m}$ is partitioned into subgraphs as indicated in Figure 2, where each $G_{i}$ is a subgraph $C_{n} P_{m_{i}}$ . Let $S$ be a dominating set for $G$ and $S_{i} = S \cap V (G_{i})$ . Then $\begin{matrix} (1) & w (S) \geq \sum_{i = 1}^{t} w (S_{i}) . \end{matrix}$ Note that in computing $w (S_{i})$ we consider $S_{i}$ to be a subset of $V (G)$ , not of $V (G_{i})$ (this affects the computation of $N [S_{i}]$ ). To verify the inequality, note that the following inequalities are equivalent: $\begin{aligned} w (S) & \geq \sum_{i = 1}^{t} w (S_{i}) \\ 5 | S | - | N [S] | & \geq \sum_{i = 1}^{t} (5 | S_{i} | - | N [S_{i}] |) \\ 5 | S | - | N [S] | & \geq \sum_{i = 1}^{t} 5 | S_{i} | - \sum_{i = 1}^{t} | N [S_{i}] | \\ | N [S] | & \leq \sum_{i = 1}^{t} | N [S_{i}] | . \end{aligned}$ The last inequality is satisfied, since each vertex in $N [S]$ is counted at least once by the expression on the right.

Note that $S_{i}$ is a set that dominates all the vertices of $G_{i}$ except possibly some vertices in the top or bottom row of $G_{i}$ (or in the cases of $G_{1}$ and $G_{t}$ , in the bottom row and top row, respectively). Let us say that a set that dominates a cylinder $G$ , with the exception of some vertices on the top or bottom edges, almost dominates $G$ . Given a cylinder $H = C_{n} P_{m_{i}}$ (namely, one of the $G_{i}$ ), What we want to know is the value of $\begin{matrix} (2) & min_{A} w (A), \end{matrix}$ taking the minimum over sets $A$ that almost dominate $H$ and computing $w (A)$ as if $A$ were a subset of a larger graph $C_{n} P_{m_{i} + 2}$ in which $H$ occupies the middle $m_{i}$ rows, or in the case of $G_{1}$ or $G_{t}$ , $A$ is a subset of $C_{n} P_{m_{i} + 1}$ in which $H$ occupies the top $m_{i}$ rows. If we can compute this minimum for (small) fixed $m_{i}$ and any $n$ , we can choose $G_{1}$ through $G_{t}$ with a small number of rows and get lower bounds on $w (S_{i})$ for any dominating set $S$ of the original $C_{n} P_{m}$ .

3. The Algorithm

We describe the algorithm for $G_{1}$ and $G_{t}$ (which of course are isomorphic); the algorithm for the other graphs $G_{i}$ is nearly identical, and we describe it more briefly. Imagine a cylinder $C_{n} P_{m}$ with a designated subset $S$ of the vertices. Recall that the vertices are denoted by $v_{i, j}$ , $1 \leq i \leq n$ , $1 \leq j \leq m$ (say, numbering left to right and bottom to top). We describe a column, say column number $i$ , in such a diagram by a state vector $s$ , in which $s_{j}$ is $0$ if vertex $v_{i, j}$ is in $S$ , $1$ if vertex $v_{i, j}$ is adjacent to a member of $S$ in column $i$ or column $i - 1$ , and $2$ otherwise. For example, the second column from the right in Figure 1 has state vector $(1, 1, 0, 1, 2, 1, 1, 0, 1, 2, 1, 0)$ . Let $| s |$ denote the number of zeros in $s$ .

Given a state vector $s$ , we append a column 0 at the left of $P_{n} P_{m}$ . Let $X$ be the set of vertices in this column corresponding to the 0 entries in $s$ , and let $Y$ be the set of vertices corresponding to the 2 entries in $s$ . An $(s, t)$ -almost-domination of $P_{n} P_{m}$ is a subset $S$ of the vertices such that $X \cup S$ dominates the first $n - 1$ columns of $P_{n} P_{m}$ and the elements of $Y$ , except possibly vertices in the first (i.e., bottom) row, and for which the state vector of the final column is $t$ .

Suppose $S$ is a subset of the vertices of $P_{i} P_{j}$ and denote by $w_{i, j} (S)$ the value of $w (S)$ computed in $P_{i + 1} P_{j + 1}$ , in which $P_{i} P_{j}$ occupies the top $j$ rows and leftmost $i$ columns. Let $w_{i, j} (s, t) = min_{S} w_{i, j} (S),$ taking the minimum over all $(s, t)$ -almost-dominations of $P_{i} P_{j}$ . If there is no $(s, t)$ -almost-domination of $G_{i, j}$ , let $w_{i, j} (s) = \infty$ .

Finally, to compute the desired minimum (equation 2), we compute $min_{s} w_{i, j} (s, s),$ since an $(s, s)$ -almost-domination of $P_{i} P_{j}$ almost dominates $C_{i} P_{j}$ .

Let $P (t)$ be the set of state vectors $u$ such that $u$ is the state vector of the next to last column in an $(s, t)$ -almost-domination of $P_{n} P_{m}$ . Then $w_{n, m} (s, t) = min_{u \in P (t)} (5 | t | - nd (u, t) + w_{n - 1, m} (s, u)),$ where $nd (u, t)$ , the number of newly dominated vertices, may be computed as follows.

$nd = 0$

For each $j = 1, \dots, m$ for which $t_{j} = 0$ and $u_{j} = 2$ , add 1 to $nd$ . This counts the newly dominated vertices $v_{n - 1, j}$ .

For each $j = 1, \dots, m$ for which $t_{j} \leq 1$ and $u_{j} \geq 1$ , add 1 to $nd$ . This counts the newly dominated vertices $v_{n, j}$ .

For each $j = 1, \dots, m$ for which $t_{j} = 0$ , add 1 to $nd$ . This counts the newly dominated vertices $v_{n + 1, j}$ .

If $t_{1} = 0$ , add 1 to $nd$ . This counts the newly dominated vertex below vertex $v_{n, 1}$ , recalling that we compute $w (S)$ in $P_{n} P_{m}$ with an extra bottom row.

Now, given some $n$ , the algorithm to compute $w_{n, m} (s, t)$ , $i = 1, \dots, n$ , is:

Initialization. Set $w_{0, m} (s, u) = 0$ if $u = s$ , and $\infty$ otherwise.

Iteration. Suppose that $i \leq n$ and that $w_{i - 1, m} (s, u)$ has been computed for all $u$ . Then for each $t$ , set $w_{i, m} (s, t) = min_{u \in P (t)} (5 | t | - nd (u, t) + w_{i - 1, m} (s, u)) .$

Thus, for fixed $m$ and any $n$ , we can compute $min_{s} w_{n, m} (s, s)$ , by computing $w_{i, m} (s, t)$ for all $s$ , $t$ , and $1 \leq i \leq n$ . Of course, what we want is to know this value for any $n$ without an infinite amount of work. Livingston and Stout [5] and Fisher [6] independently thought of looking for a sort of periodicity in the values of $γ (P_{n} P_{m})$ for fixed $m$ . Since they succeeded, we might hope that for fixed $m$ , there are $N$ , $p$ , and $q$ so that for $n \geq N$ and all $s$ and $t$ , $w_{n, m} (s, t) = w_{n - p, m} (s, t) + q .$ In this case, after a finite amount of computation, we could determine $min_{s} w_{n, m} (s, s)$ for all $n$ .

It is easy to modify the algorithm so to check for this periodicity. When we do this, we find that for $n \geq 65$ , $min_{s} w_{n, 10} (s, s) = min_{s} w_{n - 1, 10} (s, s) + 1 = n .$ Thus, for $m \geq 20$ and $n \geq 64$ , if $S$ is a dominating set in $C_{n} P_{m}$ , $w (S) \geq \sum_{k = 1}^{t} w (S_{k}) \geq w (S_{1}) + w (S_{t}) \geq 2 n,$ using the inequality (1), and so $| S | \geq (m n + 2 n) / 5.$ José Juan Carreño et al.[2] have independently arrived at the same conclusion, using a substantially different algorithm. When $n ≅ 0 (\mod 5)$ , $(m n + 2 n) / 5$ is also known to be an upper bound, so that $γ (C_{n} P_{m}) = (m n + 2 n) / 5$ (in fact, this is known to be correct for $n \geq 5$ ). The implication, of course, is that for optimal $S$ , $w (S_{k}) = 0$ for $1 < k < t$ , when $n ≅ 0 (\mod 5)$ . This is not true in general, so we improve our lower bound by computing a lower bound on $w (S_{k})$ , $1 < k < t$ .

The only change required is to redefine an $(s, t)$ -almost-domination as follows: Given a state vector $s$ , we append a column 0 at the left of $P_{n} P_{m}$ . Let $X$ be the set of vertices in this column corresponding to the 0 entries in $s$ , and let $Y$ be the set of vertices corresponding to the 2 entries in $s$ . An $(s, t)$ -almost-domination of $P_{n} P_{m}$ is a subset $S$ of the vertices such that $X \cup S$ dominates the first $n - 1$ columns of $P_{n} P_{m}$ and the elements of $Y$ , except possibly vertices in the top and bottom rows, and for which the state vector of the final column is $t$ . Corresponding to this change, in the computation of $n d$ , we add a sixth step:

If $t_{m} = 0$ , add 1 to $nd$ . This counts the newly dominated vertex above $v_{n, m}$ , recalling that we compute $w (S)$ in $C_{n} P_{m}$ as if it occupies the middle $m$ rows of a copy of $C_{n} P_{m + 2}$ .

Proceeding as before, we find that $min_{s} w_{n, 10} (s, s) = min_{s} w_{n - 5, 10} (s, s)$ , when $n \geq 12$ . Specifically, we find that $min_{s} w_{n, 10} (s, s)$ is 0, 6, 5, 9, or 6 as $n$ is 0, 1, 2, 3, or 4 $(\mod 5)$ . Thus, with $a$ equal to 0, 6, 5, 9, or 6 as appropriate, we find that $| S | \geq \frac{1}{5} ((m + 2) n + ⌊ \frac{m - 20}{10} ⌋ \cdot a) .$ That is, lower bounds for the domination number of $C_{n} P_{m}$ , when $m \geq 20$ and $n \geq 64$ , are: $\begin{aligned} \frac{(m + 2) n}{5}, & n \equiv 0 (\mod 5) \\ \frac{(m + 2) n}{5} + \frac{6}{5} ⌊ \frac{m - 20}{10} ⌋, & n \equiv 1 (\mod 5) \\ \frac{(m + 2) n}{5} + ⌊ \frac{m - 20}{10} ⌋, & n \equiv 2 (\mod 5) \\ \frac{(m + 2) n}{5} + \frac{9}{5} ⌊ \frac{m - 20}{10} ⌋, & n \equiv 3 (\mod 5) \\ \frac{(m + 2) n}{5} + \frac{6}{5} ⌊ \frac{m - 20}{10} ⌋, & n \equiv 4 (\mod 5) . \end{aligned}$ Known upper bounds (see [1]) for the domination number of $C_{n} P_{m}$ are: $\begin{aligned} \frac{(m + 2) n}{5}, & n \equiv 0 (\mod 5) \\ \frac{(m + 2) n}{5} + \frac{7}{40} (m + 2), & n \equiv 1 (\mod 5) \\ \frac{(m + 2) n}{5} + \frac{1}{10} (m + 2), & n \equiv 2 (\mod 5) \\ \frac{(m + 2) n}{5} + \frac{2}{5} (m + 2), & n \equiv 3 (\mod 5) \\ \frac{(m + 2) n}{5} + \frac{1}{5} (m + 2), & n \equiv 4 (\mod 5) . \end{aligned}$

For $n \equiv 2 (\mod 5)$ the lower and upper bounds are quite close, but for the other non-zero values of $n mod 5$ there is considerable room for improvement. It seems likely that the upper bounds are closer to the true values, as our computation allows vertices on the boundary (that is, the top and bottom rows) of the subgraphs $G_{k}$ to remain undominated. A small increase in the value of $a$ in each case would eliminate most of the gap.

When $m mod 10$ is non-zero, we have effectively ignored one of the $G_{i}$ , that is, used zero as a lower bound for one of the $w (S_{i})$ . We can improve our lower bounds very slightly (by a small constant) by correcting this. For example, for $m > 20$ and $m \equiv 8 (\mod 10)$ , we can let all but one of the $G_{i}$ have height 10, and the remaining (interior) graph, say $G_{2}$ , have height 8. Then we run the algorithm again for height 8 graphs. While we have in fact done the additional computations, the improvement is very slight, so we omit the results.

Our approach gives us lower bounds for $m \geq 20$ ; Crevals [7] computes exact values for $m \leq 22$ and all $n$ . He also computes exact values for $n \leq 30$ and all $m$ . In the course of our computations, we also obtain lower bounds for $12 \leq n < 64$ (with only $n > 30$ of interest due to the Crevals results), but they do not seem sufficiently illuminating to include here.

References:

Pavlic, P.O.L.O.N.A. and Zerovnik, J., 2013. A note on the domination number of the Cartesian products of paths and cycles. Kragujevac Journal of Mathematics, 37(2), pp.275-285.
Carreño, J.J., Martínez, J.A. and Puertas, M.L., 2020. A general lower bound for the domination number of cylindrical graphs. Bulletin of the Malaysian Mathematical Sciences Society, 43, pp.1671-1684.
Guichard, D.R., 2004. A lower bound for the domination number of complete grid graphs. Journal of Combinatorial Mathematics and Combinatorial Computing, 49, pp.215-220.
Gonçalves, D., Pinlou, A., Rao, M. and Thomassé, S., 2011. The domination number of grids. SIAM Journal on Discrete Mathematics, 25(3), pp.1443-1453.
Livingston, M. and Stout, Q.F., 1994. Constant time computation of minimum dominating sets. Congressus Numerantium, pp.116-128.
Fisher, D.C., 1993. The domination number of complete grid graphs. preprint.
Crevals. S., 2014. Domination of cylinder graphs. Congressus Numerantium, 219, pp.53–63.

[1] Pavlic, P.O.L.O.N.A. and Zerovnik, J., 2013. A note on the domination number of the Cartesian products of paths and cycles. Kragujevac Journal of Mathematics, 37(2), pp.275-285.

[2] Carreño, J.J., Martínez, J.A. and Puertas, M.L., 2020. A general lower bound for the domination number of cylindrical graphs. Bulletin of the Malaysian Mathematical Sciences Society, 43, pp.1671-1684.

[3] Guichard, D.R., 2004. A lower bound for the domination number of complete grid graphs. Journal of Combinatorial Mathematics and Combinatorial Computing, 49, pp.215-220.

[4] Gonçalves, D., Pinlou, A., Rao, M. and Thomassé, S., 2011. The domination number of grids. SIAM Journal on Discrete Mathematics, 25(3), pp.1443-1453.

[5] Livingston, M. and Stout, Q.F., 1994. Constant time computation of minimum dominating sets. Congressus Numerantium, pp.116-128.

[6] Fisher, D.C., 1993. The domination number of complete grid graphs. preprint.

[7] Crevals. S., 2014. Domination of cylinder graphs. Congressus Numerantium, 219, pp.53–63.

Contents

Journal of Combinatorial Mathematics and Combinatorial Computing

A New Lower Bound for the Domination Number of Complete Cylindrical Grid Graphs

Abstract

1. Introduction

2. Getting a Lower Bound

3. The Algorithm

References:

Information

Guidelines

CP Initiatives

Follow CP