\(k\)-domination and \(k\)-tuple total domination for some chessboard graphs

Proof. Since every vertex in the \(n \times n\) bishop’s graph has a degree of less than \(2n-1\) the first part of the theorem holds. Likewise, since for even \(n\) every vertex in the \(n \times n\) bishop’s graph has a degree of less than \(2n-3\), the theorem holds. ◻

Proof. Note that for odd \(n\) every square other than the center square is adjacent to most \(2n-4\) squares for \(n>1\). It follows that all these squares must be occupied. Next, consider the center square. This square is adjacent to \(2n-2\) squares. Thus, this square can be left unoccupied. ◻

Proof. First, consider the formation of bishops where bishops are placed in every square except the squares in the columns to the immediate left and right of the center column. There, place bishops in every square except the squares to the immediate left and right of the center square, along with unoccupied squares below each of these initial two unoccupied squares. Figure 1, below, illustrates.

Consider the central \(3 \times 3\) sub-board. Each of these squares is adjacent to \(2n-4\) squares, except for the center square (this square is adjacent to \(2n-2\) squares). Thus, all our unoccupied squares are adjacent to \(2n-4\) squares and must have all their adjacent squares occupied. It follows that \(\gamma_{2n-4}(B_n) \leq n^2-4\) for odd \(n>1\).

To see that \(\gamma_{2n-4}(B_n) \geq n^2-4\), first note that all squares not in the central \(3 \times 3\) sub-board are all adjacent to less than \(2n-4\) squares. Thus, all these squares must be occupied. All that is left to consider is the central \(3 \times 3\) sub-board and its corresponding induced subgraph. Taking the lower left corner as a dark square, the induced subgraph corresponding to the vertices associated with the light squares in our \(3 \times 3\) sub-board forms a cycle of \(4\) vertices. Thus, any unoccupied squares among these four light-colored squares of our central \(3 \times 3\) sub-board cannot be adjacent to any other unoccupied square. It follows that we can have at most \(2\) unoccupied squares in the light-colored squares of our central \(3 \times 3\) sub-board.

Next, consider the subgraph induced by the vertices associated with the dark colored squares of our central \(3 \times 3\) sub-board. Note first that the center square is adjacent to the other four dark-colored squares in our \(3 \times 3\) sub-board. Since these four other squares are all adjacent to exactly \(2n-4\) squares, it follows that the center square must be occupied. Likewise, none of the unoccupied squares associated with the dark squares in our \(3 \times 3\) sub-board can be adjacent. It follows that we can have at most two unoccupied, dark-colored squares and at most two unoccupied, light-colored squares in our center most \(3 \times 3\) sub-board. Thus, we can have at most four unoccupied squares. ◻

Proof. Given odd \(n>3\), consider a formation of bishops as follows. Every square outside of the central \(3 \times 3\) sub-board is occupied. Also occupied are all the squares in the center column. The only unoccupied squares are in our central \(3 \times 3\) sub-board and are also in the far left and far right columns of the central \(3 \times 3\) sub-board. Figure 2, below, illustrates.

Note that in the above formation of bishops, it is easy to see that any of our unoccupied squares has, at most, one unoccupied adjacent square. Since each of the unoccupied squares is adjacent to \(2n-4\) squares, it is easy to see that we have a \(2n-5\) dominating set of bishops. Thus, \(\gamma_{2n-5}(B_n) \leq n^2-6\).

Next, we must show that \(\gamma_{2n-5}(B_n) \geq n^2-6\). As in Theorem 2.3, we must consider the central \(3 \times 3\) sub-board and its corresponding squares. This follows from the fact that the squares outside of this sub-board are adjacent to less than \(2n-5\) squares and therefore must be occupied. We then have the same induced subgraphs associated with the light and dark squares of our central \(3 \times 3\) sub-board that we considered in Theorem 2.3. For the subgraph that is a cycle of four vertices (associated with the central light-colored squares), note that if we have at least three unoccupied squares among these squares, then we have one of these unoccupied squares with two adjacent unoccupied squares. This is not possible since these four squares all have degree \(2n-4\). Thus, among the central light-colored squares we can have, at most, two unoccupied squares.

Finally, consider the corresponding subgraph induced by the vertices associated with the five central dark-colored squares. The center square is adjacent to exactly \(2n-2\) squares. The four central dark-colored squares are each adjacent to \(2n-4\) squares. Thus, we can have, at most, one unoccupied adjacent square for each of these four squares. The center square is adjacent to these four squares. It follows that if the center square is unoccupied, there can be no other unoccupied square among these five squares. However, if one leaves the other four dark central squares unoccupied, then these squares are each adjacent to exactly \(2n-5\) occupied squares. It follows that we can have, at most, four unoccupied squares among the five central dark-colored squares. Thus, we can have, at most, six unoccupied squares in our \(3 \times 3\) sub-board and the entire \(n \times n\) board. ◻

Proof. First, consider a formation of bishops with every square occupied except two of the four central squares. We leave unoccupied two central squares that are nonadjacent. Figure 3, below, illustrates one such formation of bishops for a \(8 \times 8\) board.

To see that the set is a \(\gamma_{2n-3}(B_n)\)-set, consider the two squares that are not occupied. These squares are each adjacent to exactly \(2n-3\) other squares. Since all the other squares are occupied and the two unoccupied squares are not adjacent, we have a \(\gamma_{2n-3}(B_n)\)-set.

To see that this is a minimum \(\gamma_{2n-3}(B_n)\)-set, first note that all squares that are not among the four central squares are adjacent to, at most, \(2n-5\) other squares. Thus, all the squares other than the four central squares must be occupied. Next, consider the four central squares. The subgraph induced by the vertices associated with the four central squares gives us two components. Both of these components are paths of two vertices. Thus, each of these components must have, at most, one unoccupied square associated with it. It follows that we can have at most two unoccupied squares and still have a \(\gamma_{2n-3}(B_n)\)-set. ◻

Proof. Consider a formation of bishops where every square is occupied except for the four central squares. To show that this formation of bishops is a \(2n-4\)-dominating set, consider the squares other than the four central squares. They are adjacent to, at most, \(2n-5\) other squares. Thus, these squares must be occupied. It follows that \(\gamma_{2n-4}(B_n)\geq n^2-4\).

Next, consider the four central squares. It follows that since these squares all are adjacent to exactly \(2n-3\) other squares, and these squares are only adjacent to one unoccupied square, then we have a \(\gamma_{2n-4}(B_n)\)-set. Thus, \(\gamma_{2n-4}(B_n) \leq n^2-4\). ◻

Proof. Begin by labeling the columns of our \(n \times n\) board from left to right, \(1\) to \(n\), and labeling the rows, bottom to top, \(1\) to \(n\). Consider the formation of bishops where every square is occupied except for the squares in column \(\frac{n}{2}-1\) (from rows \(\frac{n}{2}-1\) to \(\frac{n}{2}+1\)) and in column \(\frac{n}{2}+2\) (from rows \(\frac{n}{2}-1\) to \(\frac{n}{2}+1\)). Figure 4, above, illustrates.

To show that this formation forms a \(\gamma_{2n-5}(B_n)\)-set, consider the \(16\) squares in the center-most \(4 \times 4\) sub-board. The outermost \(12\) squares in this sub-board are all adjacent to exactly \(2n-5\) other squares. Note that the unoccupied squares are adjacent to exactly \(2n-5\) other squares and all these squares are occupied. Thus, we have a \(\gamma_{2n-5}(B_n)\)-set. It follows that \(\gamma_{2n-5}(B_n) \leq n^2-6\).

Next, to see that \(\gamma_{2n-5}(B_n) \geq n^2-6\), we first note that all squares outside of our central \(4 \times 4\) sub-board must be occupied since all these squares are not adjacent to at least \(2n-5\) squares. We will now consider the \(8\) light-colored squares in our central \(4 \times 4\) sub-board, without loss of generality, noting that this case is symmetric to considering the \(8\) dark-colored squares in this same sub-board. We must show that no more than \(3\) unoccupied, light-colored squares are possible for this central \(4 \times 4\) sub-board.

To show this, first consider the case where there are exactly \(2\) light-colored squares in our central \(2 \times 2\) sub-board left unoccupied. The remaining \(4\) light colored squares in our central \(4 \times 4\) sub-board are all adjacent to one of these unoccupied squares and are all adjacent to exactly \(2n-5\) squares. Thus, all these squares must be occupied. This leaves us with, at most, \(3\) unoccupied, light-colored squares for this case.

Next, consider the case for which exactly \(1\) of our two light-colored squares in the central \(2 \times 2\) sub-board is left unoccupied. Since both of these sub-cases are symmetric, consider either sub-case, without loss of generality. There are only \(2\) remaining light colored squares in our central \(4 \times 4\) sub-board that are not adjacent to this unoccupied square for these subcases. The \(2\) light-colored squares are adjacent and both of these squares are adjacent to \(2n-4\) other squares. Thus, only one of these two squares can be unoccupied. We then have at most \(2\) unoccupied light-colored squares possible for the central \(4 \times 4\) sub-board for this case.

Finally, consider the case where the upper left and lower right squares in our central \(2 \times 2\) sub-board are occupied. There are exactly \(4\) remaining light-colored squares in our central \(4 \times 4\) sub-board. The square in the upper left corner of this central \(4 \times 4\) sub-board is adjacent to the square in the lower right corner of the same sub-board. Both of these squares are light colored. It follows that because both of these squares are adjacent to exactly \(2n-5\) squares, only one of these squares can be unoccupied. This leaves us with, at most, \(3\) light-colored, unoccupied squares possible for our central \(4 \times 4\) sub-board. ◻

Proof. Consider the border squares of our \(n \times n\) board. There are \(4(n-1)\) of these squares. Let \(a\) be the number of bishops placed along the border of the board and \(b\) be the number of bishops placed in the interior of the board. Note that each bishop placed along the border of the board attacks at most \(2\) unoccupied squares along the border. Also, note that each bishop placed in the interior attacks at most \(4\) unoccupied squares along the border. This gives us the following inequality: \(k(4(n-1)-a) \leq 2a+4b\). This reduces to \(4k(n-1) \leq (k+2)a+4b\). But since \(k \geq 2\), then \(a+b \geq \frac{4k(n-1)}{k+2}\). ◻

Proof. First, note squares on the \(i^{th}\) border are adjacent to exactly \(n-3+2i\) other squares. Thus, since we take \(k=n-1+2j\), the first \(j\) borders must be occupied. Note that in the \(i^{th}\) border there are \(4(n-2i+1)\) squares. Note that for \(j=0\) it follows that we then have \(0=(k-n+1)(3n-k-1)\) bishops forced to be placed in a border due to a lack of adjacent squares.

Next, note that for the other cases where \(j>0\), we must have at least \(\sum_{i=1}^{j}4(n-2i_+1)=(k-n+1)(3n-k-1)\) bishops placed on the first \(j\) borders. We also note that each square in the interior, and not in the first \(j\) borders, is adjacent to exactly \(4\) squares in any one of the first \(j\) borders. Thus, if we consider the squares in the \(j+1\) border, there are exactly \(2(k-n+1)\) bishops in the first \(j\) occupied borders adjacent to any square in the \(j+1\) border. Thus, if a square in the \(j+1\) border isn’t occupied, it needs an additional \(k-2(k-n+1)=2n-k-2\) bishops not in any of the first \(j\) borders to be adjacent to it.

Next, we define \(a\) to be the number of bishops in the \(j+1\) border and \(b\) to be the number of bishops not placed in the first \(j+1\) borders but placed in the interior of the board. Note then that we have \(4(n-1-2j)-a=4(2n-k-2)-a\) squares in the \(j+1\) border that are not occupied. Note that any square in the \(j+1\) border can be adjacent to, at most, two other unoccupied squares from squares in the \(j+1\) border. Likewise, squares not in the first \(j+1\) borders can be adjacent to, at most, four squares in the \(j+1\) border. This leads to the following inequality: \((4(2n-k-2)-a)(2n-k-2) \leq 2a+4b\). This reduces to \(4(2n-k-2)^2 \leq(2n-k)a+4b\). However, since by assumption \(\frac{k-n+1}{2}=j \leq \frac{n-5}{2}\), then \(4(2n-k-2)^2 \leq (2n-k)a+(2n-k)b\), or \(a+b \geq \frac{4(2n-k-2)^2}{2n-k}\). Finally, it follows that \(\gamma_{n-1+2j}(B_n) \geq a+b+(k-n+1)(3n-k-1) \geq \frac{4(2n-k-2)^2}{2n-k}+(k-n+1)(3n-k-1)\). ◻

Proof. First note that squares on the \(i^{th}\) border are adjacent to exactly \(n-3+2i\) other squares. Thus, if we take \(k=n-2+2j\), then we must have the first \(j\) borders filled with bishops. Thus, for the case where \(j=0\), we are forced to place \(0=(3n-k-2)(k-n+2)\) bishops due to a lack of adjacent squares.

Next, consider the cases where \(j>0\). For this case, we must have \(\sum_{1}^{j}4(n-2i+1)=(3n-k-2)(k-n+2)\) bishops from the first \(j\) borders (since there are \(4(n-2i+1)\) squares in the \(i^{th}\) border and all the first \(j\) borders must be occupied). We also note that each square in the interior, and not in the first \(j\) borders, is adjacent to exactly \(4\) squares in any one of the first \(j\) borders. Thus, if we consider the squares in the \(j+1\) border, there are exactly \(2(k-n+2)\) bishops in the first \(j\) occupied borders adjacent to any square from this border. Thus, if a square in the \(j+1\) border isn’t occupied, it needs an at least additional \(k-2(k-n+2)=2n-k-4\) bishops not in any of the first \(j\) borders to be adjacent to it.

Next, we define \(a\) to be the number of bishops in the \(j+1\) border and \(b\) to be the number of bishops not placed in the first \(j+1\) borders but placed in the interior of the board. Note that we have \(4(n-1-2j)-a=4(2n-3-k)-a\) squares in the \(j+1\) border that aren’t occupied. Note that squares in the \(j+1\) border are adjacent to at most \(2\) other unoccupied squares from the \(j+1\) border, and squares not in the first \(j+1\) borders are adjacent to, at most, \(4\) unoccupied squares from the \(j+1\) border. Thus, we have the following: \((4(2n-3-k)-a)(2n-k-4) \leq 2a+4b\). However, since by assumption \(\frac{k-n+2}{2}=j \leq \frac{n}{2}-2\), then \(4(2n-k-3)(2n-k-4) \leq (2n-k-2)a+(2n-k-2)b\), or \(a+b \geq \frac{4(2n-k-3)(2n-k-4)}{2n-k-2}\). Finally, it follows \(\gamma_{n-1+2j}(B_n) \geq a+b+(3n-k-2)(k-n+2) \geq \frac{4(2n-k-3)(2n-k-4)}{2n-k-2}+(3n-k-2)(k-n+2)\). ◻

Proof. For proof of this theorem, first note that if we plug in \(k=2\) into the lower bound found in Theorem 2.8, we find that \(\gamma_2(B_n) \geq 2n-2\). Thus, all that needs to be shown is that \(\gamma_2(B_n) \leq 2n-2\).

To do this, consider a formation of bishops with every square that is in either the middle column or the middle row occupied by bishops, with the exception of three squares. These three unoccupied squares are the top-most square and the bottom-most square in the middle column, along with the square in the middle column that is two rows up from the center-most square. Finally, we place bishops in the squares to the immediate upper left and the immediate upper right of the center-most square. Figure 5, shown below, illustrates. It is straightforward to see that this forms a \(2\)-dominating set of size \(2n-2\) for odd \(n>3\). Thus, \(\gamma_2(B_n) \leq 2n-2\) for odd \(n>3\). ◻

Proof. We begin the proof by considering a formation that has bishops placed in every square of the two center columns. Note that bishops placed in either one of these columns is a standard dominating set. Thus, the set itself is a \(2\)-dominating set. ◻

Proof. Since all border squares are adjacent to exactly \(n-1\) other squares, and every square is adjacent to at least one border square, it follows that we can have no empty squares. ◻

Proof. To begin consider a formation of bishops (for \(n>2\)) with all the squares occupied except for the top row and left-most column. To see that this is a \(\gamma_{\times n-2,t}(B_n)\)-set of bishops, first note that any border square is adjacent to, at most, one empty square. Thus, since the vertices corresponding to the border squares are each of degree \(n-1\), we have all border squares adjacent to at least \(n-2\) bishops.

Next, consider the interior squares. All of the corresponding vertices for these squares have a degree of at least \(n+1\) and are adjacent to at most \(3\) empty squares. It is clear that these squares are adjacent to at least \(n-2\) bishops in our set.

For the count on the number of bishops, note that a row or column each has \(n\) squares in them. Thus, since the upper left square of the board is counted twice in the empty row and column, we have exactly \(n^2-2n+1\) bishops in our formation. ◻

Proof. It is clear that because of Theorem 2.14, all that must be shown is that for all \(n>2\), \(\gamma_{\times n-2,t}(B_n) \geq n^2-2n+1\). To see Theorem 2.15 holds, note first that every square that is not in the corner of our board or in the center most square of our board is adjacent to at least two border squares that are not corner squares of our board. Consider the \(4(n-2)\) squares along the border that are not corner squares. It follows that since these squares have an associated degree of \(n-1\), they can be adjacent to at most one unoccupied square. It then follows that we can have at most \(2(n-2)\) unoccupied squares among the squares not in the \(4\) corners of our board, or in the center most square of our board.

Note also that if the center most square of our board is unoccupied then we can not have any of our corner squares unoccupied. This is because it would force a corner square to be adjacent to two unoccupied squares. Similarly, if we leave any square along the main diagonal unoccupied, except one of the corner squares on this main diagonal, then we cannot have an empty corner square for either of the corner squares in this main diagonal. Thus, we can have at most \(2n\) unoccupied squares on our board with \(4\) of the unoccupied squares being corner squares and none of the empty squares being interior squares that are in either of the main diagonals. It then follows that if we have \(2n\) empty squares, these empty squares must all be along the border of our board, with four of these empty squares being corner squares.

Next, note that the \(n \times n\) bishop’s graph consists of exactly two components. These two components are associated with the dark and light squares of our board. Assign the lower-left hand square as dark colored. Note that the four corners of the board are in the component associated with the dark squares. It is the case that if we are to have \(2n\) unoccupied squares, then we must have exactly \(n-1\) of these unoccupied squares among the light squares (since the light squares contain no corner squares and there are exactly \(2(n-1)\) light border squares). Suppose then that we have exactly \(2n\) unoccupied squares on our board. Thus, we must have \(n+1\) empty squares among the dark squares.

Consider the \(2n-4\) unoccupied border squares that are not corner squares. Note that any one of these squares is adjacent to exactly two other border squares. However, these two adjacent border squares have another common neighbor along the edge of the board other than the original unoccupied square. It follows that we cannot have an unoccupied square for this second common neighbor, since the other common neighbor was our original unoccupied square. Thus, all our unoccupied squares must come in adjacent pairs of squares assigned along the border of our board.

Consider the four interior squares that are immediately diagonally adjacent to our four corner squares. These are the squares that would be corner squares of our board if the border squares were removed. Note that any of these squares is adjacent to exactly \(n+1\) other squares, including two unoccupied corner squares. It follows that any of these four squares can be adjacent to, at most, one other empty square.

Now we will consider the four squares of degree \(n+1\) considered above. We will show inductively that one of these four squares will be forced to be adjacent to exactly four unoccupied squares, which is a contradiction. Begin by considering the square in the second column (from the left) and the second row (from the top), without loss of generality by symmetry. This square must have exactly one more adjacent empty square other than the two unoccupied corner squares adjacent to this square. Since this square is not an interior square, then either the square in the top row and third column (left to right), or the square in the third row (top to bottom) and the left most column must be unoccupied. We can then assume by symmetry that the unoccupied square is in the far left column, third row down from the top. This unoccupied square needs to be paired adjacently with another unoccupied square. The only square left that can be unoccupied is the square in the third column (right to left) bottom row, which we must leave unoccupied.

Next, consider the square (if it exists) that is in the fourth row down, second column (left to right). This square has exactly \(n+1\) adjacent squares. Thus, it can only have at most three adjacent unoccupied squares. Note that in order to have our \(2n\) unoccupied squares, every border square that is not a corner square must have exactly one unoccupied square adjacent to it. There must then be an unoccupied square assigned to either the square in the far left column, five rows down, or the square in the top row, five columns from the left. It is the case that we cannot have unoccupied squares assigned in both of these squares, or else the square in the fourth row down, second column to the left, would have four adjacent unoccupied squares, which is a contradiction.

Consider the square in the far left column, four rows down. There are two possibilities for assigning an adjacent pair of unoccupied squares (with one of those unoccupied squares being adjacent to the considered square). One way would be to assign an adjacent pair of unoccupied squares in the far left column, five rows down, and the other unoccupied square in the bottom most row, fifth column (right to left). The other way to assign unoccupied squares is to have an empty square in the top most row, fifth column (from the left), and an unoccupied square in the far right column, fifth row (from the bottom).

For the former case of assigning adjacent pairs described, we then would consider the one of squares in either row six (top to bottom), column two (from the left) or the square in column six (from left to right) and row two (from top to bottom). Which of these two squares to consider would depend upon which square is adjacent to both of our previously assigned, unoccupied, adjacent pair of squares. The chosen square would have degree \(n+1\) and will force another adjacent pair of unoccupied squares along the border on a common negative sloping diagonal.

The process would continue by assigning an adjacent pair of unoccupied border squares along negative sloping diagonals in this manner. In order to have \(n+1\) unoccupied dark squares, we would have adjacent unoccupied border squares assigned to either the negative sloping diagonal that is third from the far left or third from the far right.

In the former case, consider the dark square that would be the lower, far left corner square if the border squares were removed. This square is adjacent to exactly \(4\) unoccupied squares. This is not possible since it is of degree \(n+1\). In the latter case, a similar contradiction occurs for the square that would be the upper right corner of our board if the border squares were removed. ◻

Proof. First we will show that \(\gamma_{\times n-2,t}(B_n) \leq n^2-2n\) by giving a formation of \(n^2-2n\) bishops that provide a \(\gamma_{\times n-2,t}(B_n)\)-set. For this formation, place bishops in every dark-colored square in the leftmost column and every light-colored square in the rightmost column, except for any corner squares in either of these columns. Next, place bishops in every square in the top row, except the \(2\) corner squares in this row. Finally, place bishops on every interior square of our board. Leave all the other squares unoccupied. It is easy to see that any border square is adjacent to at most \(2\) unoccupied squares. It is also easy to see that any other square is adjacent to at most \(3\) unoccupied squares. Thus, since the border squares are adjacent to \(n-1\) squares and the interior squares are adjacent to at least \(n+1\) squares, we have a \(\gamma_{\times n-2,t}(B_n)\)-set. To see that this set has exactly \(n^2-2n\) bishops, note that we have \((n-2)^2=n^2-4n+4\) bishops in the interior of our board. We also have exactly \(2n-4\) bishops placed on the border of our board.

To see that \(\gamma_{\times n-2,t}(B_n) \geq n^2-2n\), note that every square is adjacent to at least \(2\) squares along the border of our board. Also note that any of these border squares can be adjacent to, at most \(1\) unoccupied square. Thus, since we have \(4(n-2)\) border squares that are not corner squares, we can have, at most, \(2(n-2)=2n-4\) unoccupied squares. Thus, since we have \(4\) corner squares, there are at most \(2n\) unoccupied squares on our board. ◻

Proof. Consider the formation with all interior squares occupied and all border squares unoccupied. It follows that each border square has only two of its \(n-1\) neighbors unoccupied. Thus, these squares are not taken into account. The other squares have a degree of at least \(n+1\) and are adjacent to four empty border squares. It follows that \(\gamma_{\times n-3,t}(B_n) \leq n^2-4n+4\). Now, all that needs to be shown is that \(\gamma_{\times n-3,t}(B_n) \geq n^2-4n+4\).

We begin the second part of our proof by introducing a term first found in [1]. A “rectangle” of squares is a set of squares along four diagonals. These two positive- and two negative-sloping diagonals aren’t in the long diagonals and share exactly four border squares as the intersections of two of these four diagonals. Any border square in a “rectangle” is adjacent to exactly two other border squares which themselves have another common adjacent square along the border and in this “rectangle”. All these squares in these four diagonals, including these four border squares, are part of the “rectangle”. Figure 6, above, illustrates. In Figure 6, one of the \(6\) “rectangles” is highlighted by placing bishops in every square of it.

Consider any of the \(n-2\) “rectangles” of our board. There are five cases to go through. These cases begin with the case where the border squares of a given “rectangle” are all occupied and the final case where the case that a given “rectangle” has all of its border squares unoccupied. We will show that for any of the cases there can be, at most, four unoccupied squares in a given “rectangle”. This would give us at most \(4(n-2)\) unoccupied squares in the squares that are not corner squares, and at most \(4n-4\) unoccupied squares.

The first case is where none of the unoccupied squares in our “rectangle” are border squares. Consider any of these border squares in this “rectangle”. It follows that the squares adjacent to this border square can have at most \(2\) unoccupied squares among them. Next, consider the other border square in this “rectangle” that is not adjacent to the first border square considered in this “rectangle”. In a similar fashion, there can be, at most \(2\) unoccupied squares adjacent to this square. Thus, there can be at most \(4\) unoccupied squares in this “rectangle”.

Next, consider the case where there is exactly one border square in our “rectangle” unoccupied. There can be at most two other unoccupied squares adjacent to this border square. These two unoccupied squares cannot be on the same diagonal, or we would have a border square of our “rectangle” adjacent to three unoccupied squares. Since any of these border squares are adjacent to exactly \(n-1\) other squares, this is a contradiction.

There are three subcases to consider since we can have at most two unoccupied squares adjacent to one unoccupied border square in our “rectangle”. The first subcase is that there are exactly two unoccupied squares adjacent to our one unoccupied border square. Again, these two unoccupied squares must come from different diagonals. The second subcase is that we have exactly one unoccupied square adjacent to our considered unoccupied border square. The third subcase is that we have no unoccupied squares adjacent to our considered unoccupied border square.

Thus, for our first subcase, consider the two unoccupied border squares in our “rectangle” that are adjacent to the unoccupied border square. These two border squares are adjacent to two unoccupied squares thus far. Also, these two border squares are in the other two diagonals of our “rectangle” and these occupied border squares can be adjacent to at most two unoccupied squares. Thus, there can be no more unoccupied squares in our “rectangle” other than these three unoccupied squares. It follows that since any “rectangle” can have at most \(4\) unoccupied squares in it, we have less than \(4n-4\) unoccupied squares on our board.

The next subcase is that we have exactly one unoccupied square adjacent to the original unoccupied border square of our “rectangle”. Since both of these unoccupied squares are adjacent to a second border square, we cannot have any more unoccupied squares adjacent to it. This leaves us with one diagonal left to consider for this subcase. This diagonal can have, at most one unoccupied square or we would have a border square adjacent to three unoccupied squares. Thus, we can have at most three unoccupied squares in any “rectangle” for this subcase.

The final subcase we will consider is when the unoccupied border square in our “rectangle” has no unoccupied square adjacent to it. There are then two diagonals left to consider in our “rectangle”. These two diagonals contain another border square in our “rectangle” that is not adjacent to our unoccupied border square from our “rectangle”. Since this square can have at most two unoccupied squares adjacent to it, we must have at most three unoccupied squares in our “rectangle”. This finishes the second case.

Next, consider the case for which we have exactly two of the border squares in our “rectangle” unoccupied. Note that these unoccupied border squares must be adjacent if we wish to have more than \(2\) unoccupied squares in our “rectangle”. This is because if we had a third unoccupied square and two unoccupied border squares in our “rectangle” which are not adjacent, we would then have a border square of our “rectangle” adjacent to at least three unoccupied squares.

There are then two subcases to consider for this case. These subcases are where we have either one unoccupied square or no unoccupied squares in the diagonal of our “rectangle” that does not contain either of our two unoccupied border squares in the “rectangle”. This is because if we had more than one unoccupied square on this considered diagonal, we would have a border square adjacent to at least three unoccupied squares. For the former subcase, it follows that we can have no unoccupied squares that are not border squares on the diagonals that contain exactly one of our unoccupied border squares. Thus, we can have at most \(3\) squares in this “rectangle” for this subcase.

For the next subcase, we have two adjacent, unoccupied border squares on the same “rectangle” and no unoccupied square in the diagonal of our “rectangle” that does not contain either of our unoccupied border squares. Note that the two remaining diagonals of our “rectangle” can each contain only one more unoccupied square, or we would have a border square with three or more adjacent unoccupied squares. Thus, we have proved the third case.

Finally, consider the fourth and fifth cases for which we have three or four unoccupied border squares in our “rectangle”. It follows that we must have a pair of unoccupied border squares that are not adjacent. In a manner similar to the case with exactly two unoccupied border squares that are not adjacent, we can have no additional unoccupied squares in our “rectangle”. This leaves us with at most \(4\) unoccupied squares in this “rectangle” for our final two cases. ◻

Proof. It is easy to see that since every square of our \(n \times n\) board for either graph is adjacent to at most \(8\) squares the theorem holds. ◻

Proof. To see Theorem 3.2, note that the border squares are adjacent to at most \(5\) squares. It follows that these squares must be occupied. Next, consider the other squares. The interior squares are all adjacent to \(8\) other squares. It follows that we cannot have two adjacent unoccupied squares.

This makes our problem equivalent to the king’s independence problem for a \((n-2) \times (n-2)\) board (but we think of our unoccupied squares as independent kings). As noted by [19], the solution of the king’s independence problem for the \(n \times n\) board is \((\left\lceil\frac{n}{2}\right\rceil)^2\). Thus, our number of empty squares is exactly \((\left\lceil\frac{n}{2}\right\rceil-1)^2\). ◻

Proof. To begin, note that any of our squares along the border, or that would be along the border if the border squares were removed, have less than \(8\) adjacent squares. It follows that all of these \(8(n-2)\) squares must be occupied.

In a similar manner as in Theorem 4.2 we’re then left with the knight’s independence problem on a \((n-4) \times (n-4)\) board. As noted in [19] for an \(n \times n\) board the maximum number of independent knights is \(\left\lceil\frac{n^2}{2}\right\rceil\). Thus, there will be \(\left\lceil\frac{(n-4)^2}{2}\right\rceil\) empty squares in our minimum \(k\) dominating set of knights. This means that we will have \(\left\lfloor\frac{(n-4)^2}{2}\right\rfloor\) additional knights in our \((n-4) \times (n-4)\) sub-board. ◻

Proof. Note that for even \(n\) every square has less than \(4n-4\) squares adjacent to it. The theorem then follows. ◻

Proof. First note that every square besides the four center squares all have corresponding vertices of degree less than \(4n-5\). Thus, every square other than the center four squares must be occupied. First, note that the degrees of the vertices associated with the four center squares are all less than \(4n-5\). Consider the subgraph induced by the vertices associated with the four center squares. It is a complete graph of four vertices. Thus, we can only have one empty square. Taking any one of the four center squares as unoccupied and all the other squares as occupied yields the formation of queens. ◻

Proof. Note that every square other than the four center squares all have corresponding degrees of less than \(4n-6\). Thus, all these squares must be occupied. Also, since the subgraph associated with the center squares is a complete graph of four vertices, and the four center squares have exactly \(4n-5\) adjacent squares, there can be at most two unoccupied squares. Leaving any two of the four center squares unoccupied gives us the formation of queens. ◻

Proof. First, note that all squares not located in the central \(4 \times 4\) sub-board have less than \(4n-7\) adjacent squares. Therefore, all \(n^2-16\) of these squares are occupied. This leaves us with the \(16\) most central squares in our board. Consider the formation of queens show in Figure 7.

This formation of queens is formed by filling in the outermost \(n^2-16\) squares with queens. Then, we fill in the four center squares with queens. This leaves us to consider the twelve remaining squares that border the four center squares. We then occupy all these squares except the four squares to be described. To describe these squares, label the rows from \(1\) to \(n\) (from bottom to top) and the columns from \(1\) to \(n\) (left to right). Then, leave the square in row \(\frac{n}{2}-1\) and column \(\frac{n}{2}+1\) unoccupied along with the square in row \(\frac{n}{2}+2\) and column \(\frac{n}{2}\). Also, leave the square from row \(\frac{n}{2}\) and column \(\frac{n}{2}-1\) unoccupied along with the square in row \(\frac{n}{2}+1\) and column \(\frac{n}{2}+2\). It is easy to verify that all the unoccupied squares are all non-adjacent and have exactly \(4n-7\) adjacent squares. Thus, we have a \(\gamma_k(Q_n)\)-set and \(\gamma_k(Q_n)\leq n^2-4\).

To see that \(\gamma_k(Q_n)\geq n^2-4\), there are five cases to consider. For the first case, note that we cannot have \(4\) unoccupied squares among our four central squares. This is due to the fact that the central squares are adjacent to \(4n-5\) squares and three of those squares would be unoccupied. Further, we cannot have three central unoccupied squares and have an unoccupied square anywhere else. This leaves us with \(3\) remaining cases.

For the first of the three cases, we have exactly one of our four center squares unoccupied, say the top-left central square, without loss of generality by symmetry. It then follows that we would have only one square in column \(\frac{n}{2}-1\) left to possibly be unoccupied since all \(12\) of our squares on the border of the \(4 \times 4\) center most sub-board are all adjacent to exactly \(4n-7\) squares and the top left central square is adjacent to three of the four considered squares in this column. Similarly, there remains exactly one possible square that we could leave unoccupied from the top row of our \(4 \times 4\) center most sub-board. These two potential unoccupied squares, one in column \(\frac{n}{2}-1\) and row \(\frac{n}{2}-1\) and the other in column \(\frac{n}{2}+2\) and row \(\frac{n}{2}+2\), are both along the main positive-sloping diagonal of our board and are thus adjacent. It follows that only one of these squares can be unoccupied since they’re both of degree \(4n-7\). There are now two subcases to consider. The subcases are the subcase where one of these two squares is unoccupied and the subcase where both squares are occupied.

For the first subcase note that by symmetry along the negative sloping main diagonal, we can consider either of these two squares along the main positive-sloping diagonal as unoccupied, without loss of generality. Thus, we leave the square in the upper right corner of our central \(4 \times 4\) sub-board unoccupied. It follows that there is only one possible square that can be unoccupied since all \(12\) of the squares on the border of our central \(4\times 4\) sub-board are adjacent to exactly \(4n-7\) squares. This square is in row \(\frac{n}{2}-1\) and in column \(\frac{n}{2}+1\). Thus, we can have no more than \(3\) unoccupied squares for this subcase.

Next, consider the subcase where the two squares in the main positive-sloping diagonal and on the edge our central \(4 \times 4\) sub-board are occupied. There are only two additional squares that could then be potentially unoccupied. These squares are in row \(\frac{n}{2}-1\) and column \(\frac{n}{2}+2\), and also in row \(\frac{n}{2}+2\) and column \(\frac{n}{2}-1\). These squares are also adjacent to each other and \(4n-7\) total squares. It then follows that we can have at most \(2\) unoccupied squares for this subcase. Thus, in the case where we have exactly one unoccupied square among the four central squares of our board, we can only have at most \(3\) unoccupied squares.

For the next case, consider the case where we have exactly two of our \(4\) central squares unoccupied. There are two subcases to consider without loss of generality by symmetry. For the first subcase, let us have the two unoccupied squares of our central \(4\) squares not be diagonally adjacent. Note that every square in our central \(4 \times 4\) sub-board is adjacent to one of these two unoccupied squares. Thus, for this subcase we can have no more unoccupied squares. It then follows that we can only have exactly \(2\) unoccupied squares for this subcase.

Next, consider the subcase for which our two unoccupied squares from our four center squares are diagonally adjacent. Let these unoccupied squares be from the main positive-sloping diagonal, without loss of generality by symmetry. It follows that we have exactly \(2\) squares in our central \(4 \times 4\) sub-board that are not adjacent to either of these \(2\) unoccupied squares. These squares are the upper left and lower right corners of our central \(4 \times 4\) sub-board, along the main negative-sloping diagonal. It follows for this subcase that since these two squares are adjacent, we can have at most \(3\) unoccupied squares for this subcase. Thus, for the case where exactly two of the central four squares are unoccupied, we can have at most \(3\) unoccupied squares.

Finally, consider the case for which each of the four central squares is occupied. It follows that since the remaining squares that could potentially be unoccupied are adjacent to \(4n-7\) squares, we cannot have adjacency between unoccupied squares. Thus, since we have exactly four rows and four columns to choose our potential unoccupied squares, we can have at most \(4\) unoccupied squares. ◻

Proof. Note that all the squares are adjacent to at most \(4n-4\) other squares. Thus, all squares must be occupied. ◻

Proof. Since all of squares not in the center are adjacent to less than \(4n-5\) squares, then all these squares must be occupied. Thus, if we leave the center square unoccupied and every other square occupied, we form a minimum \(4n-4\) dominating set. ◻

Proof. The proof for Theorem 4.7 follows by considering a formation of queens placed in every square but the center square. This gives us a \(4n-5\) dominating set of queens. To see that this is a minimum dominating set of queens, note that every square but the center square is adjacent to at most \(4n-6\) squares. Thus, all these squares must be occupied. ◻

Proof. First, note that all squares outside of the central \(3 \times 3\) sub-board must be occupied since these squares are adjacent to at most \(4n-8\) squares. We then consider the formation of queens in which every square is filled except for the square to the immediate left of the center square and the square to the immediate upper right of the center square. It is easy to see that since the unoccupied squares aren’t adjacent and both are adjacent to exactly \(4n-6\) squares, then we have a \(4n-6\) dominating set. Thus, \(\gamma_{4n-6}(Q_n) \leq n^2-2\).

To see that this is a minimum \(4n-6\) dominating set of queens, note that the center square is adjacent to every other square in our central \(3 \times 3\) sub-board. Thus, if we have this square unoccupied, we could not have any more squares unoccupied since the other squares in the central \(3 \times 3\) sub-board are all adjacent to \(4n-6\) squares. Thus, to have a minimum \(4n-6\) dominating set of queens, the center square must be occupied. This leaves us with the squares along the border of our central \(3 \times 3\) sub-board to consider. Note that none of the unoccupied squares can be adjacent to each other. This is because all these squares are adjacent to exactly \(4n-6\) squares. There are two cases to consider. This follows since we can have, at most, \(1\) unoccupied square in a corner of our central \(3 \times 3\) sub-board.

For the first case, consider any one of the corner squares of our central \(3 \times 3\) sub-board to be unoccupied, namely the bottom left corner of our sub-board, without loss of generality due to symmetry. There are two squares from the border of our central \(3 \times 3\) sub-board that are not adjacent to this unoccupied square. These squares are the square directly above the center square and the square directly to the right of the center square. It is easy to see that these two squares are diagonally adjacent. Thus, only one of them could be unoccupied. Thus, for this case, we can have at most \(2\) unoccupied squares.

Next, consider the case where the \(4\) corner squares of the central \(3 \times 3\) sub-board are occupied. There are \(4\) squares that can potentially be unoccupied in this case. They are the squares immediately above and below the center square and to the immediate left and right of the center square. Note that all these squares are adjacent to each other and a total of \(4n-6\) squares. It follows that for this case we can have at most \(1\) unoccupied square. Thus, there can be at most \(2\) unoccupied squares for any of these cases. ◻

Proof. First, note that all squares outside of the central \(3 \times 3\) sub-board must be occupied since these squares are adjacent to at most \(4n-8\) squares. Also, all squares in the central \(3 \times 3\) sub-board except for the center square are adjacent to \(4n-6\) squares. The center square is adjacent to \(4n-4\) squares. Thus, if one of the squares in our central \(3 \times 3\) sub-board (except the center square) is unoccupied, then it can be adjacent to, at most, one other unoccupied square. The center square, if unoccupied, can have at most three adjacent unoccupied squares. There are then two cases.

Let us then consider the first case where the center square is not occupied. It follows that if any of the other squares is unoccupied, then that square can be adjacent to no other unoccupied square. Thus, let us consider the subcase for which one of the four squares on the edge of our central \(3 \times 3\) sub-board is unoccupied. For the first subcase, let this unoccupied square not be one of the four corners of this \(3 \times 3\) sub-board. We can assume without loss of generality due to symmetry that the square directly above the center square is unoccupied. This leaves us with two possible squares that could also be unoccupied. These two squares are the bottom two corner squares of our central \(3 \times 3\) sub-board. However, since these squares are adjacent to each other and also adjacent to the center square, we can have only one of these squares unoccupied. This leaves us with exactly three unoccupied squares for this sub-case.

Next, consider the other subcase for which the center square is unoccupied, along with one of the four corner squares of our central \(3 \times 3\) sub-board. Without loss of generality due to symmetry, take the unoccupied square to be the upper right corner square of our central \(3 \times 3\) sub-board. There are then exactly two other squares that could also be unoccupied. These squares are the square immediately below the center square and the square to the immediate left of the center square. However, since these squares are adjacent, only one of them can be unoccupied. This leaves us with at most three unoccupied squares.

Finally, consider the case for which the center square is occupied. If there are \(4\) or more unoccupied squares, then there will be two unoccupied squares that are row adjacent and two unoccupied squares that are column adjacent. Let us start with the column adjacent pair of unoccupied squares, without loss of generality due to symmetry. For this case, note that the row adjacent pair of unoccupied squares must be in the third remaining row not adjacent to either of the column adjacent pair of unoccupied squares. However, at least one of them must be adjacent to one of the unoccupied column-adjacent squares. It follows that we can have, at most, three unoccupied squares for this case. ◻

Proof. The theorem follows since every border square has \(3n-3\) squares adjacent to it and every square is adjacent to a border square. ◻

Proof. First, consider the case for which we have an unoccupied square along the border of our board. It follows that we can have no other unoccupied square except another square on the border that is adjacent to the first unoccupied border square. This is the case since if we had an unoccupied border square and another unoccupied square not adjacent to the unoccupied border square, then there would be a common neighbor along the border of the board. This common neighbor would then have \(2\) adjacent unoccupied squares. However, since the border squares have \(3n-3\) squares adjacent to them, they can have at most one adjacent unoccupied square. Thus, when we have one of our unoccupied squares along the border of our board, we have at most two unoccupied squares.

Consider the case for which all of our border squares are occupied. Note then that any interior square is adjacent to exactly \(8\) border squares. It follows that since any border square can be adjacent to at most one unoccupied square and there are \(4(n-1)\) border squares, then for all \(n>4\), \(\gamma_{\times 3n-4,t}(Q_n) \geq n^2-\left\lfloor\frac{n-1}{2}\right\rfloor\). ◻

Proof. Let \(a\) be the number of queens placed on the border of our board and \(b\) be the number of queens placed in the interior of the board. We note that any queen placed in any of the corner squares of the board can attack at most \(2n-1\) squares along the border. Note that the corner squares attack at least as many squares in the border as the other border squares. Also note that any queen on the interior of the board can attack at most \(8\) unoccupied squares along the border. We then have the following inequality: \(k(4(n-1)-a) \leq (2n-1)a+8b\). However, since \(n \geq 4\) and \(k \geq 2\), we have \(2n-1+k>8\). Thus, \(4k(n-1) \leq (2n-1+k)(a+b)\) or \(\gamma(Q_n) \geq \frac{4k(n-1)}{2n-1+k}\). ◻

Proof. First note that if we take \(k=3n-3+2j\), then we must have the first \(j\) borders filled with queens – as squares on the \(i^{th}\) border have associated vertices of degree \(3n-5+2i\). Thus, we must have at least \(\sum_{i=1}^{j}(4(n-2i+1)=(k-3n+3)(5n-k-3)\) queens in the first \(j\) borders, since there are \(4(n-2i+1)\) squares in the \(i^{th}\) border and all the first \(j\) borders must be occupied.

It suffices to show that there are at least \(4(4n-k-4)=4(n-1-(k-3n+3))=4(4n-k-4)=4(n-1-2j)=4(n-2(j+1)+1)\) queens on the board other than the queens on the first \(j\) borders. Note that this is exactly the number of squares in the \(j+1\) border. Thus, if we have \(r\) unoccupied squares in the \(j+1\) border, then there must be at least \(r\) occupied squares outside of the first \(j+1\) borders.

To see that this is the case, first note that any square in the \(j+1\) border is adjacent to exactly \(3n-5+2(j+1)=3n-3+2j\) other squares. Thus, since \(k=3n-3+2j\), it follows that any unoccupied square in the \(j+1\) border must have all of its adjacent squares occupied. Note that we cannot have more than \(4\) unoccupied squares in our \(j+1\) border, or else there would be two adjacent unoccupied squares in our \(j+1\) border. Thus, since any unoccupied square on the \(j+1\) border cannot have adjacent unoccupied squares, we cannot have more than \(4\) unoccupied squares on our \(j+1\) border.

Next, note that the squares outside of our first \(j\) borders form a \((n-2j) \times (n-2j)\) sub-board. It also follows that since all of the corner squares of this \((n-2j) \times (n-2j)\) sub-board are adjacent and in the \(j+1\) border, we can have only one of these squares unoccupied.

Let \(r\) be the number of unoccupied squares in our \(j+1\) border. Note that if \(r=0\), then we are done. Also, note that the squares outside of our first \(j+1\) borders form a \((n-2j-2) \times (n-2j-2)\) sub-board. Next, note that any square in the \(j+1\) border that is a corner square of our \((n-2j)\times (n-2j)\) sub-board is adjacent to exactly \(n-2j-2=n-(k-3n+3)-2\) squares in our central \((n-2j-2) \times (n-2j-2)\) sub-board. Note also that any square on the \(j+1\) border that is not a corner square of the \((n-2j) \times (n-2j)\) sub-board is adjacent to exactly \((n-(k-3n+3)-2)+(n-(k-3n+2)-3)\) squares in our \((n-2j-2) \times (n-2j-2)=(n-(k-3n+3)-2) \times (n-(k-3n+3)-2)\) sub-board. The first term in the previous sum is the number of squares in our \((n-2j-2) \times (n-2j-2)\) sub-board either row or column adjacent to the given unoccupied square and \(n-(k-3n+2)-3\) is the number of squares the unoccupied square is diagonally adjacent to in the \((n-2j-2) \times (n-2j-2)\) sub-board.

For our first subcase of the case where \(r=1\), let the unoccupied square of our \(j+1\) border be a corner square of our \((n-2j) \times (n-2j)\) sub-board. It suffices to show that \(n-(k-3n+3)-2 \geq r=1\), or \(4n-k \geq 6\). Note that \(n-(k-3n+3)-2\) is the number of squares in our \((n-2j-2) \times (n-2j-2)\) sub-board that are diagonally adjacent to the considered unoccupied corner square of the \((n-2j) \times (n-2j)\) sub-board. Thus, since \(k<4n-7\) this subcase of the case where \(r=1\) has been shown.

For the next subcase of the case where \(r=1\), let the unoccupied square of our \(j+1\) border not be a corner square of our \((n-2j) \times (n-2j)\) sub-board. Thus, it suffices to show that \((n-(k-3n+3)-2)+(n-(k-3n+3)-3)=8n-2k-11 \geq r=1\). It follows that since \(k<4n-7\) our case where \(r=1\) is done.

Next, let \(r \geq 2\) and \(r \leq 4\). It follows that we have two cases. Let us first consider the case for which one of the unoccupied squares in our \(j+1\) border is a corner square of the \((n-2j) \times (n-2j)\) sub-board. Consider then this unoccupied corner square of our \((n-2j) \times (n-2j)\) sub-board and another unoccupied square of our \(j+1\) border. It follows that there are at most \(2\) squares in our \((n-2j-2) \times (n-2j-2)\) sub-board adjacent to both the corner square of our \((n-2j) \times (n-2j)\) sub-board and any of the other unoccupied squares in our \(j+1\) border. Thus, it suffices to show for this subcase that \(2(n-(k-3n+3)-2)+(n-(k-3n+3)-3)-2 \geq 4 \geq r\). It follows that we have finished the case where \(2 \leq r \leq 4\) and one of the unoccupied squares of our \(j\) border is a corner square of the \((n-2j) \times (n-2j)\) sub-board since \(k<4n-7\).

Finally, consider the case for which \(2 \leq r \leq 4\) and we have no unoccupied corner square of our \((n-2j) \times (n-2j)\) sub-board. Note that since we cannot have two unoccupied squares on our \(j+1\) border squares adjacent, we have at most \(6\) squares that are commonly adjacent to any two of our unoccupied squares in the \(j+1\) border squares. The following must then be shown: \(2(n-(k-3n+3)-2)+2(n-(k-3n+3)-3)-6 \geq 4 \geq r\). Thus, since we take \(k<4n-7\), the proof is done. ◻

Proof. For the proof, note that the first \(j\) borders must be filled. There are \(\sum^j_{i=1} 4(n-2i+1)=(5n-k-4)(k-3n+4)\) squares on the first \(j\) borders.

Next, we will assume that there are exactly \(r\) squares in the \(j+1\) border that are not occupied. We will then show that there must be at least \(r\) squares occupied outside of the first \(j+1\) borders. Since there are \(4(4n-k-5)\) squares in the \(j+1\) border and \((5n-k-4)(k-3n+4)+4(4n-k-5)=(5n-k-6)(k-3n+6)\), this will provide the proof. There are \(3\) cases to consider.

Case A is the case where there are no unoccupied squares in the corner squares of the \((n-2j) \times (n-2j)\) sub-board that is formed when the first \(j\) border squares are removed. For Case B we will have exactly \(1\) unoccupied square among the corner squares of the \((n-2j) \times (n-2j)\) sub-board. For Case C we will consider the case where we have exactly \(2\) unoccupied corner squares of the \((n-2j) \times (n-2j)\) sub-board. Since all the corner squares of our \((n-2j) \times (n-2j)\) sub-board are adjacent and we can have only one unoccupied square adjacent to any of the unoccupied squares in our \(j+1\) border, these \(3\) cases cover all possibilities.

For Case A, there are \(4\) subcases. The first subcase that we will consider is the case where there is no common line (whether a row, column, or diagonal) between two unoccupied squares on the edge of the center most \((n-2j) \times (n-2j)\) sub-board. For the first case of this subcase, let \(r=1\).

Note for the first case of our subcase that our unoccupied square is adjacent to an entire row (or column, without loss of generality) within our \((n-2j-2) \times (n-2j-2)\) sub-board. This means that we have row adjacency to \(n-2j-2=n-(k-3n+4)-2\) squares. Our unoccupied square is also diagonally adjacent to \(n-(k-3n+4)-3\) squares of our \((n-2j-2) \times (n-2j-2)\) sub-board. Note that only one of these squares among the adjacent squares can be unoccupied. This leaves us with at least \(2(4n-k-6)-1\) unoccupied squares. Since \(r=1\), we must have the following inequality: \(2(4n-k-6)-2 \geq 1\). However, since \(k \leq 4n-10\) by assumption we have our proof for this case of the subcase of Case A.

For our second case of this subcase, let \(2 \leq r \leq 8\). Since we can only have one square adjacent to any unoccupied square along the border, and the \(j+1\) border has only \(2\) rows and columns, this exhausts all possible values of \(r\) for the second case. Consider any two unoccupied squares on our \(j+1\) border. Note that we then must have either \(2\) rows (or columns) or a row and a column of our \((n-2j-2) \times (n-2j-2)\) central sub-board that are row (or column) adjacent to either of these unoccupied squares. Since these adjacent squares could potentially overlap only once, we have at least \(2(n-2j-2)-1=2(n-(k-3n+4)-2)-1=2(4n-k-6)-1\) such column or row adjacent squares. In addition, we have diagonally adjacent squares to these unoccupied squares. There are at least \(n-(k-3n+4)-3=4n-k-7\) diagonally adjacent squares to any of the border squares of our central \(n-2j-2\) sub-board. This gives us at least an additional \(2(4n-k-7)-1\) since we may have at most one unoccupied square diagonally adjacent to the two considered unoccupied squares.

Next, we must consider the potential squares of our \((n-2j-2) \times (n-2j-2)\) that are column (or row) adjacent and diagonally adjacent to our two considered unoccupied squares. There are at most \(2\) of these squares. Next, note that either of our two unoccupied squares can be adjacent to at most one unoccupied square. This gives us at least \(2(4n-k-6)+2(4n-k-7)-2-2\) squares of our \((n-2n-2) \times (n-2j-2)\) sub-board that are occupied. To finish this case of our subcase, we need the following inequality: \(2(4n-k-6)+2(4n-k-7)-2-2 \geq 8 \geq r\). However, since \(k \leq 4n-10\), we have our proof of the second case of our second subcase of Case A. This concludes the proof of the second subcase of Case A.

For the third sub-case of Case A, we will consider the subcase for which we have \(2\) lines in our \((n-2j-2) \times (n-2j-2)\) sub-board for which either of these lines is shared by two unoccupied squares in the \(j+1\) border. For the third sub-case of Case A we must have \(r=4\), since we can only have at most one unoccupied square adjacent to any of our unoccupied squares on the \(j+1\) border. There are now two possibilities. Since we cannot have more than one unoccupied square adjacent to any of our unoccupied squares in the \(j+1\) border, we must have the \(2\) lines adjacent to two unoccupied squares in our \(j+1\) border be either a row line and a column line or two diagonal lines.

For the first case of our third subcase of Case A consider the lines to be a row line and a column line. There are \(4n-k-6\) squares of our \((n-2j-2) \times (n-2j-2)\) sub-board row adjacent to two of our unoccupied squares on the \(j+1\) border and the same number column adjacent to two of our unoccupied squares on the \(j+1\) border. Given that the common row and column overlap once we have \(2(4n-k-6)-1\) squares that are either row-adjacent or column-adjacent to exactly two of the unoccupied squares in our \(j+1\) border.

Also, for the first case of the third sub-case of Case A, consider the diagonal lines of our \((n-2j-2) \times (n-2j-2)\) sub-board that are adjacent to one of our \(4\) unoccupied squares on the \(j+1\) border. Note that we can have at most \(6\) squares of our \((n-2j-2) \times (n-2j-2)\) sub-board where a square is diagonally adjacent to \(2\) of our unoccupied squares on the \(j+1\) border. This gives us at least \(4(4n-k-3)-6\) squares that are diagonally adjacent to at least one of our unoccupied squares on the \(j+1\) border.

We are now interested in how many squares of our \((n-2j-2) \times (n-2j-2)\) sub-board fall on a common diagonal and a common row (or column) with an unoccupied square in our \(j+1\) border. There can be at most \(4\) of these squares. Thus, we must have the following inequality: \(2(4n-k-6)-1+4(4n-k-3)-6-4 \geq 4\) to show the first case of the third sub-case of Case A. However, since \(k \leq 4n-10\), the inequality follows. This concludes the first case of the third sub-case for Case A.

We now move to the second case of the third subcase of Case A. For this case, the two lines common to two unoccupied squares in our \(j+1\) border must be diagonal lines of our \((n-2j-2) \times (n-2j-2)\) sub-board. This gives us \(4\) row or column lines of squares in our \((n-2j-2) \times (n-2j-2)\) sub-board that are adjacent to one unoccupied square in our \(j+1\) border. These lines intersect in exactly \(4\) squares. This gives us exactly \(4(4n-k-6)-4\) such squares.

Next, consider the diagonally adjacent squares of our \((n-2j-2) \times (n-2j-2)\) sub-board that are diagonally adjacent to at least one unoccupied square on our \(j+1\) border. For each pair of diagonally adjacent unoccupied squares on the \(j+1\) border, consider the squares diagonally adjacent to only one of the squares from each diagonally adjacent pair of unoccupied squares. There are \(4n-k-7\) squares diagonally adjacent to one of these squares. Since these diagonals intersect at most on one square, there are at least \(2(4n-k-7)-1\) such squares.

Finally, for the second case of the third sub-case of Case A, note that the squares that are row or column adjacent to an unoccupied square on the \(j+1\) border and are also among the \(2(4n-k-7)-1\) squares noted above number \(8\) or less. Thus, we need the following inequality to hold: \(4(4n-k-6)-4+2(4n-k-7)-1-8 \geq 4\). Since \(k \leq 4n-10\) by assumption, the theorem holds. This concludes the proof of the third sub-case of Case A.

For the final sub-case of Case A, let all corner squares of our central \((n-2j) \times (n-2j)\) sub-board be occupied and let there be diagonal adjacency between \(2\) of the unoccupied squares on the \(j+1\) border. Note for this subcase that \(2 \leq r \leq 6\), since no additional unoccupied squares can be adjacent to the diagonally adjacent pair of squares and no unoccupied square on our \(j+1\) border can be adjacent to more than one unoccupied square.

Consider the diagonally adjacent pair of unoccupied squares on our \(j+1\) border. There is exactly one row and one column of our \((n-2j-2) \times (n-2j-2)\) sub-board adjacent to these two unoccupied squares. This gives us \(2(4n-k-6)-1\) adjacent squares which must be occupied (since we have the \(1\) overlapping square). Also, consider the squares in our \((n-2j-2) \times (n-2j-2)\) sub-board that are diagonally adjacent to our pair of unoccupied diagonally adjacent squares on the \(j+1\) border. There are at least \(4n-k-7\) such squares. Thus, it is necessary to show that \(2(4n-k-6)+4n-k-7-1\geq 6 \geq r\). However, since \(k \leq 4n-10\), this final sub-case of Case A has been shown.

We now move on to Case B. This is the case where there is exactly one of the corners of our center-most \((n-2j) \times (n-2j)\) sub-board unoccupied. For our first subcase, suppose that we have diagonal adjacency between two of our unoccupied squares on the \(j+1\) border. For this to be the case, we must have exactly \(r=3\) or \(r=4\) unoccupied squares on our \(j+1\) border. Thus, we have at least one row and one column in our \((n-2j-2) \times (n-2j-2)\) sub-board where all the squares must be occupied. Considering that there is an overlap in this row and column of exactly one square, this gives us at least \(2(4n-k-6)\) occupied squares in our \((n-2j-2) \times (n-2j-2)\) sub-board.

We also have diagonals that must be occupied as well. The diagonal in our \((n-2j-2) \times (n-2j-2)\) sub-board that is adjacent to the unoccupied corner square of our \((n-2j) \times (n-2j)\) sub-board has exactly \(4n-k-6\) squares. Only one of these squares can be unoccupied. Also, consider one of the unoccupied squares which is from the pair of diagonally adjacent unoccupied squares. There are \(4n-k-7\) squares from our \((n-2j-2) \times (n-2j-2)\) sub-board that are diagonally adjacent to this square. All of these squares must be occupied.

Consider the intersections of the considered row, column, and two diagonals of our \((n-2j-2) \times (n-2j-2)\) sub-board that were considered above. There can be no more than \(5\) intersections of these lines. Thus, we need \(3(4n-k-6)+4n-k-7-5-1 \geq 4 \geq r\). However, since \(k \leq 4n-10\) by assumption this holds.

The next subcase of Case B we will consider is that we have no diagonal adjacency between two of our unoccupied squares on the \(j+1\) border. It is important to note that for this subcase \(1 \leq r \leq 6\). Let us first consider the subcase for which \(r=1\). Thus, our only unoccupied square is the corner square of our \((n-2j) \times (n-2j)\) sub-board. We then note that there are exactly \(n-(k-3n+4)-3\) squares adjacent to this unoccupied square. Since only one of these adjacent squares may be unoccupied, we need \(4n-k-7-1 \geq 1=r\) to show the proof for this subcase. However, since \(k \leq 4n-10\) by assumption, we have our proof of this subcase.

For the final subcase of Case B will assume \(2 \leq r \leq 6\). Note that there are \(n-(k-3n+4)-3\) adjacent squares to our unoccupied corner square of the \((n-2j) \times (n-2j)\) sub-board. Note also that there must be at least \(n-(n-3k+4)-3\) squares in the \((n-2j-2) \times (n-2j-2)\) sub-board that are diagonally adjacent to any other considered unoccupied square of our \(j+1\) border. Also, there are exactly \(n-(n-3k+4)-2\) squares in the \((n-2j-2) \times (n-2j-2)\) sub-board that are either row-adjacent or column-adjacent to this considered unoccupied square.

Next, note that we have an overlap of at most two squares that are diagonally adjacent to both our unoccupied corner square of the \((n-2j) \times (n-2j)\) sub-board and any other considered unoccupied square of our \(j+1\) border. Also, there is one square of our \((n-2j-2) \times (n-2j-2)\) sub-board that is adjacent to the unoccupied corner square of the \((n-2j) \times (n-2j)\) sub-board and either row or column adjacent to the other considered unoccupied square of our \(j+1\) border. Note that we can have at most \(2\) unoccupied squares in our \((n-2j-2) \times (n-2j-2)\) sub-board that are adjacent to either of our two considered unoccupied squares of our \(j+1\) border. This means that it suffices to show for this subcase that \(2(n-(k-3n+4)-3)+n-(k-3n+4)-2-2-2 \geq 6 \geq r\). However, since \(k \leq 4n-10\) by assumption, the inequality holds. This proves Case B of our proof.

For Case C there are two subcases. The first subcase is that the two unoccupied corner squares of our \((n-2j) \times (n-2j)\) sub-board are diagonally adjacent. This means that there cannot be any other unoccupied square in our \(j+1\) border. Thus, for this subcase \(r=2\). Note that for this subcase there are exactly \(n-(k-3n+4)-3\) squares in our \((n-2j-2) \times (n-2j-2)\) subboard that are adjacent to both of the considered unoccupied squares. All these squares must be occupied. Thus, we need \(n-(k-3n+4)-3 \geq 2=r\). However, since \(k \leq 4n-10\) by assumption we have the proof for this subcase of Case C.

For the next subcase, assume that the two unoccupied corner squares of our \((n-2j) \times (n-2j)\) sub-board are row adjacent (or column adjacent, without loss of generality by symmetry). Note that for this subcase \(2 \leq r \leq 4\). Note that we have \(n-(n-3n+4)-3\) squares in our \((n-2j-2) \times (n-2j-2)\) sub-board that are diagonally adjacent to each of these unoccupied squares. These two diagonals of our \((n-2j-2) \times (n-2j-2)\) sub-board must have all their squares occupied. Also, there is at most one square that is common to both of these diagonals. Thus, to prove the final subcase of Case C it suffices to show that \(2(n-(k-3n+4)-3)-1 \geq 4 \geq r\). However, since \(k \leq 4n-10\), this subcase of has been shown. This ends the proof of Case C. ◻