Connected minimum secure-dominating sets in grids

Peer review under responsibility of Kalasalingam University.

Abstract

For any (finite simple) graph $G$ the secure domination number of $G$ satisfies ${\gamma }_s\left(G\right)\ge \frac{\left|V\left(G\right)\right|}{2}$. Here we find a secure-dominating set $S$ in $G$ such that $\left|S\right|=\lceil \frac{\left|V\left(G\right)\right|}{2}\rceil$ in all cases when $G$ is a grid, and in the majority of cases when $G$ is a cylindrical or toroidal grid. In all such cases, $S$ satisfies the additional requirement that $G\left[S\right]$ is connected. We make note that the concept of secure-dominating sets considered in this paper is quite different from the other secure domination currently of interest.¹

Keywords:

• Security in graphs
• Dominating sets
• Hub sets

1 Introduction

All graphs will be finite and simple. The vertex and edge sets of a graph $G$ are denoted $V\left(G\right)$ and $E\left(G\right)$, respectively. An edge joining vertices $u$ and $v$ may be denoted $uv$ or $vu$. If $x\in V\left(G\right)$, the open neighbor set of $x$ in $G$ is $N_G\left(x\right)=\{u\in V\left(G\right):ux\in E\left(G\right)\}$. If $G$ is the only graph in the discussion, the subscript $G$ may be omitted, in this notation. For instance, we define the closed neighborhood of $x\in V\left(G\right)$ to be $N\left[x\right]=N\left(x\right)\cup \left\{x\right\}$. If $S\subseteq V\left(G\right)$, $N\left(S\right)={\cup }_{x\in S}N\left(x\right)$ and $N\left[S\right]=N\left(S\right)\cup S$. A set $S\subseteq V\left(G\right)$ is $dominating$ in $G$ if and only if $N\left[S\right]=V\left(G\right)$. A dominating set $S\subseteq V\left(G\right)$ is called a perfect dominating set if every vertex in $V\left(G\right)\setminus S$ has exactly one neighbor in $S$.

Fig. 7 A connected secure-dominating set in both $P_9\square P_{10}$ and $P_9\square C_{10}$, on 45 vertices. Edges are omitted.

Fig. 8 A connected secure-dominating set on 18 vertices in $C_6\square C_6$. Edges are omitted.

Fig. 9 A connected secure-dominating set on 25 vertices in $C_7\square C_7$. Edges are omitted.

Fig. 10 A connected secure-dominating set $C_7\square C_9$. Edges are omitted.

In an $attack$ on $S\subseteq V\left(G\right)$, in $G$, each vertex in $N\left[S\right]\setminus S$ may expend its one unit of aggression by attacking one vertex of $S$ to which it is adjacent (joined to by an edge of $G$). In a defense of $S$, each vertex of $S$ may expend its one unit of defense by defending either itself or one of its neighbors in $S$. A defense of $S$thwarts or overcomes an attack on $S$ if and only if each vertex of $S$ has at least as many defenders as attackers. $S$ is $secure$ in $G$ if and only if for every attack on $S$ there is a defense which thwarts that attack.

Suppose $X\subseteq S\subseteq V\left(G\right)$ and $|N\left(X\right)\setminus S|>|N\left[X\right]\cup S|$; that is, $X$ has more potential attackers than potential defenders. If every vertex in $N\left(X\right)\setminus S$ attacks one of its neighbors in $X$, then no matter how the defensive capabilities of $S$ are allocated, at least one vertex of $X$ will have more attackers than defenders. These observations disclose a necessary condition for security that turns out to be, in the fundamental theorem of security, sufficient.

Theorem 1.1

Brigham, Dutton, and Hedetniemi 2007; see also [1]

Suppose $G$ is a graph. A set $S\subseteq V\left(G\right)$ is secure in $G$ if and only if for any $X\subseteq S$, $|N\left[X\right]\cap S|\ge |N\left(X\right)\setminus S|$.

A set $S\subseteq V\left(G\right)$ is secure-dominating if it is both secure and dominating. As observed in [2], if $S$ is secure-dominating in $G$, then $\left|S\right|\ge \frac{\left|V\left(G\right)\right|}{2}$; otherwise, if $\left|S\right|<\frac{\left|V\left(G\right)\right|}{2}$, then $|N\left(S\right)\setminus S|=|V\left(G\right)\setminus S|>\left|S\right|$, and so $S$ has more potential attackers than defenders. Therefore, if we define the secure-domination number of $G$, ${\gamma }_s\left(G\right)$, to be the minimum cardinality of a secure-dominating set in $G$, then ${\gamma }_s\left(G\right)\ge \lceil \frac{\left|V\left(G\right)\right|}{2}\rceil \text{.}$

The interesting evidence from [2] is that for a great many common graphs such as paths, most cycles, complete multipartite graphs, n-cubes, the Petersen graph, and many more, ${\gamma }_s\left(G\right)=\lceil \frac{\left|V\left(G\right)\right|}{2}\rceil$. The only exceptions to this statement on the list above are the cycles $C_n$ on $n\equiv 2\left(\text{mod}4\right)$ vertices ($n=6,10,\dots$), for which ${\gamma }_s\left(C_n\right)=\frac{n}{2}+1$.

A $grid$ is a Cartesian product $P_m\square P_n$ of non-trivial $(m,n>1)$ paths; a cylindrical grid is a Cartesian product $P_m\square C_n$ of a non-trivial path with a cycle $(m>1\text{and}n>2)$; and a toroidal grid is a Cartesian product $C_m\square C_n$ of cycles $(m,n>2)$. We will show that if $G$ is any of the first two types of grid, then ${\gamma }_s\left(G\right)=\lceil \frac{V\left(G\right)}{2}\rceil$, and more: a secure-dominating set $S\subseteq V\left(G\right)$ can be found such that $\left|S\right|=\lceil \frac{V\left(G\right)}{2}\rceil$ and, in addition, the subgraph induced by $S$ in $G$, usually denoted $G\left[S\right]$, is connected.

In such a case we say that $S$ is a connected secure-dominating set. For arbitrary connected graphs $G$ the minimum cardinality of a connected secure-dominating set is denoted ${\gamma }_s^c\left(G\right)$. Clearly, ${\gamma }_s^c\left(G\right)\ge {\gamma }_s\left(G\right)\ge \lceil \frac{V\left(G\right)}{2}\rceil$. Our aim here is to show that equality holds throughout, in this last string of inequalities, when $G$ is one of these blankety-blank grids. We have not achieved this aim for the toroidal grids, and perhaps it is not achievable. But ${\gamma }_s^c\left(G\right)=\lceil \frac{V\left(G\right)}{2}\rceil$ does hold for better than $\frac{3}{4}$ of the toroidal grids, in a sense that will be clear.

For those interested in applications, we note that a connected secure-dominating set is a connected dominating set, which is also a connected hub set [3], and all of these are of interest in street design, transportation, and network communication problems, which often involve grid graphs with mutations (holes, loops, other deformities). Surely, in this day and age, security is a desirable property for connected dominating and connected hub sets. It is shown in [3] that every minimum connected dominating set has at most one vertex more than a minimum connected hub set. The study of connected secure hub sets is wide open, at present. Our results for connected secure dominating sets in grids may be compared with the results in [4], on connected dominating sets in grids.

2 Results

Throughout, the vertices of $P_m$ or $C_m$ will be $u_1,\dots ,u_m$, along the path or around the cycle; the vertices of $P_n$ or $C_n$ will be $v_1,\dots ,v_n$; the ordered pair $(u_i,v_j)$, a vertex of $P_m\square P_n$ or $P_m\square C_n$ or $C_m\square C_n$, will be denoted $w_{i,j}$.

Theorem 2.1

If $m,n\ge 2$ are integers, then ${\gamma }_s^c\left(P_m\square P_n\right)=\lceil \frac{mn}{2}\rceil$.

Proof

Since ${\gamma }_s^c\left(G\right)\ge \lceil \frac{\left|V\left(G\right)\right|}{2}\rceil$ for all graphs $G$, it suffices in each case to find a connected secure dominating set $S\subseteq V\left(P_m\square P_n\right)$ such that $\left|S\right|=\lceil \frac{\left|V\left(G\right)\right|}{2}\rceil$.

Case 1: $m=2$. Take $S=\{w_{1,j}:j=1,\dots ,n\}$.

Case 2: $m=4$. Take $S=\{w_{i,j}:i=2,3,j=1,\dots ,n\}$.

In these first two cases, each vertex of $V\left(P_m\square P_n\right)\setminus S$ has exactly one neighbor in $S$, so $S$ is a perfect dominating set in $G$. A defensive strategy is easy: each $w\in S$ defends itself. This opens an interesting question that we will leave for others. Which graphs admit connected secure-dominating sets, which are also perfect dominating sets? In the cases to follow, and in the proofs of Theorems 2.2 and 2.3, it will be self-evident that the proposed connected secure-dominating sets are connected and dominating, but verifying security will be more difficult. Airtight proofs based on appeals to Theorem 1.1 can be provided, but these would be lengthy and unintuitive. We prefer an informal approach, in which a defense thwarting the various possible attacks is indicated informally, and it is left to the reader to verify that no clever attack can be found. The task will be simplified by the circumstance that most of the vertices of $V\left(G\right)\setminus S$ will have a unique neighbor in $S$; we may as well assume that, in any attack, each of those vertices will attack its unique neighbor in $S$. Then the question is, What will the vertices in $V\left(G\right)\setminus S$ that have a choice do, and can their attack be thwarted? To illustrate, consider

Case 3: $m=3,n\ge 3$. Take $S=\{w_{2,j}:j=1,\dots ,n\}\cup \{w_{1,j}:j\text{odd}\}$. (See Fig. 1.)

The bottom row $w_{3,1},\dots ,w_{3,n}$ are all in $V\left(G\right)\setminus S$$(G=P_3\square P_n)$; each $w_{3,j}$ will attack $w_{2,j}$. Each $w_{1,j}$, $j$ even, has a choice of 3 vertices of $S$ to attack, unless $n$ is even and $j=n$, in which case the choice is two vertices.

To see that $S$ is secure, let us consider the first doubtful case, $n=4$, and some of 6 possible attacks. First, suppose that $w_{1,4}$ attacks $w_{1,3}$. If $w_{1,2}$ does not attack $w_{1,3}$ then let $w_{1,3}$, $w_{2,4}$, and $w_{2,3}$ defend themselves; we leave it to the reader to verify that $S^{\prime }=\{w_{1,1},w_{2,1},w_{2,2}\}$ can then defend itself whether $w_{1,2}$ attacks $w_{1,1}$ or $w_{2,2}$. If, on the other hand $w_{1,2}$ does attack $w_{1,3}$, so that $w_{1,3}$ has 2 attackers, $w_{1,2}$ and $w_{1,4}$, then obviously the only possible successful defense will start with $w_{2,4}$ defending itself, and $w_{1,3}$ and $w_{2,3}$ defending $w_{1,3}$. This leads to $w_{2,2}$ defending $w_{2,3},w_{2,1}$ defending $w_{2,2}$, and $w_{1,1}$ defending $w_{2,1}$, and this defense defeats the attack.

In another attack, suppose that $w_{1,4}$ attacks $w_{2,4}$, which then has 2 attackers. The only possible way to save the day is for $w_{2,3}$ to defend $w_{2,4}$, which is, of course, defending itself. Then if $w_{1,2}$ is not attacking $w_{1,3}$, we simply let if $w_{1,3}$ defend $w_{2,3}$, and we are back to a case in which the rest of the attack can be thwarted, regardless of what $w_{1,2}$ does. On the other hand, if $w_{1,2}$ attacks $w_{1,3}$ then $w_{1,3}$ must defend itself, and, as before, $w_{2,2}$ defends $w_{2,3},w_{2,1}$ defends $w_{2,2}$, and $w_{1,1}$ defends $w_{2,1}$.

We hope the reader, after working through these cases when $n=4$, will agree that, not only is $S$ secure for all values of $n\ge 3$ (the argument is less delicate when $n$ is odd), but also that there is a relatively simple set of military-style, battlefield instructions for each vertex in $S$, telling the vertex $x\in S$ who to defend in each of a small number $(\le 6)$ of cases, defined by how many attackers each vertex in $N\left[x\right]\cap S$ has and also, for $x=w_{2,j},1\le j<n$, when $x$ has only one attacker, whether or not $w_{2,j+1}$ is defending itself, or being defended by $w_{1,j+1}\left(j\text{even}\right)$, or neither. It would be tedious to prove that such explicit battlefield instructions produce a successful defense, and we are not going to try, but we mention this because clearly such instructions bear on applications: a successful defense can be constructed by the troops by transmission of local intelligence (right-to-left along the columns of the grid, so that $w_{2,j}$ can be apprised of what $w_{2,j+1}$ has been instructed to do), without each soldier in $S$ having to know anything about the attack around vertices of $S$ a distance $>2$ in the grid from the soldiers.

By Cases 1–3, we may now assume that both $m$ and $n$ are greater than 4.

Case 4: $m,n>4$ and $m\equiv 0\left(\text{mod}4\right)$: Take $S=\{w_{j,2}:1\le j\le m\}\cup \{w_{j,n-1}:1\le j\le m\}\cup \{w_{i,j}:i\equiv 2,3\left(\text{mod}4\right),1\le i\le m,\text{and}3\le j\le n-2\}$.

We illustrate in Fig. 2, with $m=8$ and $n=7$, and $S$ indicated by darkening $n=7$.

It is helpful to realize that for any values of $m,n>4$, $m\equiv 0\left(\text{mod}4\right)$, the set $S$ is obtainable by repeating the pattern in the first 4 rows of the $m\times n$ grid in each of the $\frac{m}{4}$ blocks of 4 rows each into which the grid can be partitioned.

With this aid to understanding, it is clear that $S$ is connected and dominating, with $\frac{mn}{2}$ vertices. The security of $S$ is much easier to see than the corresponding claim in Case 3; in the battlefield instructions to the vertices of $S$ for defending against an attack, many (must, if $n$ is large) vertices will be instructed to defend themselves, in all circumstances, and the others will have to defend a neighbor under only one local attack variation. For instance, $w_{2,2},w_{2,3}\in S$ will each defend themselves unless and only unless $w_{1,3}$ attacks $w_{1,2}$, giving $w_{1,2}$ two attackers. When this happens, $w_{2,2}$ will defend $w_{1,2}$ and $w_{2,3}$ (which has no attacker if $w_{1,3}$ is attacking $w_{1,2}$) defends $w_{2,2}$.

Case 5: $m\equiv 2\left(\text{mod}4\right),m,n>4$: Take $S=\{w_{i,2}:1\le i\le m\}\cup \{w_{i,n-1}:1\le i\le m\}\cup \{w_{i,j}:i\equiv 2,3\left(\text{mod}4\right),2\le i\le m,3\le j\le n-2\}$.

This amounts to adding two rows to the pattern for $P_{m-2}\square P_n$ that look like (with elements of $S$ darkened):

We illustrate with $m=6$, and $n$ unspecified. (See Fig. 3.)

From Cases 1–5 we are left with the cases $m,n\ge 5$, both odd.

Case 6: $m\ge 5$, $m\equiv 1\left(\text{mod}4\right),n\ge 5$, odd: Take $S=\{w_{i,2}:1\le i\le m\}\cup \{w_{i,n-1}:1\le i\le m\}\cup \{w_{i,j}:i\equiv 1,0\left(\text{mod}4\right),1\le i\le m-1,3\le j\le n-2\}\cup S_0$, where $S_0=\{w_{m,j}:j\equiv 0,3\left(\mathrm{mod}4\right),3\le j\le n-2\}$ if $n\equiv 1\left(\text{mod}4\right)$, and $S_0=\{w_{m,j}:j\equiv 2,3\left(\mathrm{mod}4\right),3\le j\le n-4\}\cup \left\{w_{m,n-2}\right\}$ if $n\equiv 3\left(\text{mod}4\right)$. See Fig. 4.

Case 7: $m\ge 7$, $m\equiv 3\left(\text{mod}4\right),n\ge 5$, odd: Take $S=\{w_{i,2}:1\le i\le m\}\cup \{w_{i,n-1}:1\le i\le m\}\cup \{w_{i,j}:i\equiv 2,3\left(\text{mod}4\right),1\le i\le m-1,3\le j\le n-2\}\cup S_0$, where $S_0$ is as in Case 6. See Fig. 5. □

Fig. 1 Case 3. Vertices in $S$ are blacked-in.

Fig. 2 A connected minimum secure dominating set of vertices in $P_8\square P_7$ with $28=\frac{8\times 7}{2}$ vertices.

Fig. 3 $P_6\square P_n$, a minimum secure dominating set which is also connected.

Fig. 4 A connected secure dominating set in $P_9\square P_{11}$.

Fig. 5 A connected secure dominating set in $P_{11}\square P_9$ with $50=\lceil \frac{99}{2}\rceil$ vertices.

Theorem 2.2

If $m\ge 2$ and $n\ge 3$ are integers, then ${\gamma }_s^c\left(P_m\square C_n\right)=\lceil \frac{mn}{2}\rceil$ except, possibly, in the cases $m\equiv 3\left(\text{mod}4\right)$, $m\ge 7$, when $n\equiv 2\left(\text{mod}4\right)$, and $m\equiv 1\left(\text{mod}4\right)$, $m\ge 9$, when $n=6$.

Proof

Suppose that $S\subseteq V\left(P_m\square P_n\right)$ is secure and dominating in $P_m\square P_n$ and that, for each $i\in \{1,\dots ,m\},w_{i,1}\in S$ if and only if $w_{i,n}\in S$. It then follows that $S$ is secure and dominating in $P_m\square C_n$, which is obtained from $P_m\square P_n$ by adding the edges $w_{i,1}{w}_{i,n},i=1,\dots ,m$; obviously $S$ is dominating in the larger graph, and it is secure because each $u\in S$ has the same set of potential attackers in $P_m\square C_n$ as in $P_m\square P_n$, and its neighbor set in $S$, in $P_m\square C_n$, contains its neighbor set in $S$ in $P_m\square P_n$; that is, it has the same set of potential attackers and has lost no potential defenders in the transition from $P_m\square P_n$ to $P_m\square C_n$.

Therefore the claim of Theorem 2.2 follows from the proof of Theorem 2.1 in all cases except, possibly, in the cases

(i)	$m=3$, $n\ge 4$, $n$ even;

(ii)	$m\ge 4$, $n=3$;

(iii)

$m$ odd, $m>3$, $n\equiv 2\left(\text{mod}4\right)$, $n\ge 6$.

The reduction to these cases from the proof of Theorem 2.1 uses, of course, the obvious isomorphism of $C_n\square P_m$ and $P_m\square C_n$.

Since we are giving up on the cases $m\equiv 3\left(\text{mod}4\right)$ under (iii), and $m\equiv 1\left(\text{mod}4\right)$, $m\ge 9$, $n=6$, we need only verify the claim of the theorem in cases (i), (ii), and ${\left(\mathrm{iii}\right)}^{\prime }$: $m\equiv 1\left(\text{mod}4\right)$ and $n\equiv 2\left(\text{mod}4\right)$, ($n\ge 10$), or $m=5$ and $n=6$. For practical purposes it is worth noting that in case ${\left(\mathrm{iii}\right)}^{\prime }$ the secure-dominating sets to be given are also secure-dominating in $P_m\square P_n$, adding to the supply of minimum secure-dominating sets in plain grids. The new secure-dominating sets in case (ii), for $P_m\square C_3$, are not dominating for $P_m\square P_3$.

In the cases $m=3$, $n$ even $(n\ge 4)$, it turns out that the secure dominating set in $P_3\square P_n$ given in the proof Theorem 1, Case 3, is also secure and dominating in $P_3\square C_n$, even though the variety of attacks to be thwarted has increased with the addition of the edges $w_{i,1}{w}_{i,n},i=1,2,3$. As in the proof of Theorem 2.1, we leave it to the reader to verify this claim, most usefully by providing battlefield instructions to the vertices of $S$ for reacting to any attack. Anyone who found such instructions for the $P_3\square P_n$ case (n even) will find that they have not much changed, in fact, they will become simpler, in that instructions to the vertices $w_{2,j},j$ odd, will be pretty much the same, for different $j$.

For $P_m\square C_3$, $m\ge 4$, let $S$ be as follows.

(1)	If $m\equiv 0\left(\text{mod}4\right)$, take $S=\{w_{i,1}:1\le i\le m\}\cup \{w_{i,2}:i\equiv 2,3\left(\text{mod}4\right)\}$.

(2)	If $m\equiv 1\left(\text{mod}4\right)$, $S=\{w_{i,1}:1\le i\le m\}\cup \{w_{i,2}:i\equiv 2,3\left(\text{mod}4\right)\}\cup \left\{w_{m-1,2}\right\}$.

(3)	If $m\equiv 2\left(\text{mod}4\right)$, $S=\{w_{i,1}:1\le i\le m\}\cup \{w_{i,2}:i\equiv 2,3\left(\text{mod}4\right),1\le i\le m-2\}\cup \left\{w_{m,2}\right\}$.

(4)	If $m\equiv 3\left(\text{mod}4\right)$, $S=\{w_{i,1}:1\le i\le m\}\cup \{w_{i,2}:i\equiv 2,3\left(\text{mod}4\right),1\le i\le m-3\}\cup \{w_{m-2,2},w_{m-1,2}\}$.

The cases $m\equiv 1\left(\text{mod}4\right)$, $n\equiv 2\left(\text{mod}4\right)$, $m=5$ if $n=6$, divide into 2 subcases.

(1)	$m=5$, $n=6$: $S=\{w_{i,j}:i\in \{2,4\},1\le j\le 6\}\cup \{w_{3,2},w_{3,4},w_{3,5}\}$ (see Fig. 6).

(2)

$m\equiv 1\left(\text{mod}4\right)$, $m\ge 5$, $n\equiv 2\left(\text{mod}4\right)$, $n\ge 10$: $S=\{w_{i,j}:1\le i\le m,j\in \{2,n-1\}\}\cup \{w_{i,j}:i\equiv 2,3\left(\text{mod}4\right),2\le i\le m-3,3\le j\le n-2\}\cup \{w_{m-1,j}:3\le j\le n-2\}\cup \{w_{m-2,j}:j\equiv 2,3\left(\text{mod}4\right),3\le j\le n-7\}\cup \{w_{m-2,n-4},w_{m-2,n-2}\}$. □

Fig. 6 A connected secure-dominating set in both $P_5\square P_6$ and $P_5\square C_6$, on 15 vertices. Edges are omitted.

(See Figs. 7^{Fig. 8Fig. 9}–10.)

Theorem 2.3

Suppose that $m,n\ge 3$ are integers. Let $G=C_m\square C_n$. Then ${\gamma }_s^c\left(G\right)=\lceil \frac{mn}{2}\rceil$ except, possibly, in the following cases:

(1)	$\{m,n\}=\{6,z\}$, $z\equiv 1\left(\text{mod}4\right)$, $z\ge 9$ ;

(2)	$m\equiv n\equiv 2\left(\text{mod}4\right)$, and $m,n\ge 10$ ;

(3)	$m\equiv n\equiv 3\left(\text{mod}4\right)$, and $m,n\ge 11$ ;

(4)	$\{m,n\}=\{4r+2,4s+3\}$ for some $r\ge 1$, $s\ge 0$.

Proof

Let us say that a pair $(m,n)$ is $good$ if and only if ${\gamma }_s^c\left(C_m\square C_n\right)=\lceil \frac{mn}{2}\rceil$. Obviously $(m,n)$ is good if and only if $(n,m)$ is good.

As at the beginning of the proof of Theorem 2.2, we observe that if $S$ is a secure-dominating set of vertices in $P_m\square C_n$ such that $w_{1,j}\in S$ if and only if $w_{m,j}\in S$ then $S$ is also secure-dominating in $C_m\square C_n$. Applying this observation to the secure-dominating sets in the proof of Theorem 2.2, some of which were imported from the proof of Theorem 2.1, we find that $(m,n)$ is good in the following cases,

(i)	$\{m,n\}=\{3,z\}$, $z\ge 4$, $z\not\equiv 2\left(\text{mod}4\right)$, Look at the cases $P_m\square C_3$, $m\ge 4$, in the proof of Theorem 2.2.

(ii)	$\{m,n\}=\{4k,z\}$ for some $k\ge 1$, $z\ge 4$. See the proof of Theorem 2.1 in the cases $m=4$ and $m>4$, $m\equiv 0\left(\text{mod}4\right)$.

(iii)

$\{m,n\}=\{4r+1,4s+2\}$, $r,s\ge 1$, except for $\{4r+1,6\}$, $r\ge 2$. In the proof of Theorem 2.2, inspect the cases $P_5\square C_6$ and $P_m\square C_n$, $m\equiv 1\left(\text{mod}4\right)$, $n\equiv 2\left(\text{mod}4\right)$, $n\ge 10$.

Therefore, to finish the proof, it will suffice to show that the following pairs $(m,n)$ are $good$:

(a)

$(3,3)$;

(b)	$m=6$, $n\equiv 2\left(\text{mod}4\right)$, $n\ge 6$;

(c)	$m=7$, $n\equiv 3\left(\text{mod}4\right)$, $n\ge 7$;

(d)	$m,n>4$, $m$ odd, $n\equiv 1\left(\text{mod}4\right)$.

Here are the secure-dominating sets that show that $(m,n)$ is a good pair, in these cases.

(a)	$m=n=3$: $S=\{w_{i,1}:1\le i\le 3\}\cup \{w_{1,2},w_{2,2}\}$

(b)	$m=6$, $n\equiv 2\left(\text{mod}4\right)$, $n\ge 6$: $S=\{w_{i,j}:i\in \{2,5\},1\le j\le n\}\cup \{w_{i,j}:i\in \{3,4\},j\equiv 2,3\left(\text{mod}4\right),2\le j\le n-2,\}\cup \{w_{3,n-1},w_{4,n-1}\}$

(c)	$m=7$, $n\equiv 3\left(\text{mod}4\right)$, $n\ge 7$: $S=\{w_{i,j}:i\in \{2,6\},1\le j\le n\}\cup \{w_{i,j}:i\in \{3,4,5\},j\equiv 2,3\left(\text{mod}4\right),1\le j\le n-1,\}\cup \{w_{3,n-2},w_{5,n-2}\}$

(d)	$m,n>4$, $m$ odd, $n\equiv 1\left(\text{mod}4\right)$: $S=\{w_{i,j}:i\in \{2,m-1\},1\le j\le n\}\cup \{w_{i,j}:3\le i\le m-2,j\equiv 2,3\left(\text{mod}4\right),1\le j\le n-3,\}\cup \{w_{i,n-1}:3\le i\le m-2\}\cup \{w_{i,n-2}:3\le i\le m-2,i\text{odd}\}$.

Determining ${\gamma }_s^c\left(C_m\square C_n\right)$ in the cases left open by Theorem 2.3 is a worthy problem. We remark that it is easy to see that ${\gamma }_s^c\left(C_3\square C_n\right)\le \lceil \frac{3n}{2}\rceil +1$, for all $n$. In the other cases we can show that ${\gamma }_s^c\left(C_m\square C_n\right)\le \lceil \frac{mn}{2}+\frac{m-4}{2}\rceil$, but feel that some clever person will soon surpass this estimate. □

Notes

Peer review under responsibility of Kalasalingam University.

1 The other sort of secure domination: A dominating set $S\subseteq V\left(G\right)$ is secure dominating (in G) if and only if for every $v\in V\left(G\right)\setminus S$ there is some $u\in S$ such that $(S\setminus \left\{u\right\})\cup \left\{v\right\}$ is dominating, in G.