On the domatic numbers of queens graphs

1. Introduction

Let $G=(V,E)$ be a graph with vertex set $V$ of order $n=|V|$, and edge set $E$, of size $m=|E|$. Given an edge $uv\in E$, we say that vertices $u$ and $v$ are adjacent and that they are neighbors. The (open) neighborhood of a vertex $u\in V$ is the set $N(u)=\{v:uv\in E\}$ of neighbors of $u$. The degree of a vertex is $deg(u)=|N(u)|$, the number of neighbors of vertex $u$. The minimum degree of a vertex in a graph $G$ is denoted by $\delta (G)$. The closed neighborhood of a vertex $u$ is the set $N[u]=N(u)\cup \{u\}$.

A set $S\subset V$ of vertices is independent if no two vertices in $S$ are adjacent. The vertex independence number $\alpha (G)$ equals the maximum cardinality of an independent set in $G$.

1.1. Dominating sets

A set $S\subset V$ is a dominating set if every vertex in $V–S$ is adjacent to at least one vertex in $S$. The domination number $\gamma (G)$ is equal to the minimum cardinality of a dominating set in $G$. A minimum cardinality dominating set is called a $\gamma$-set. The upper domination number $\mathrm{\Gamma }(G)$ is equal to the maximum cardinality of a minimal dominating set in $G$.

A set $S$ is an independent dominating set if it is both an independent set and a dominating set. The independent domination number $i(G)$ is equal to the minimum cardinality of an independent dominating set in $G$. A comprehensive treatment of independent domination is given in the 2013 survey by Goddard and Henning [5].

A set $S$ is a total dominating set if every vertex in $V$ is adjacent to at least one vertex in $S$. The total domination number ${\gamma }_t(G)$ is equal to the minimum cardinality of a total dominating set in $G$. A minimum cardinality total dominating set is called a ${\gamma }_t$-set. The upper total domination number ${\mathrm{\Gamma }}_t(G)$ is equal to the maximum cardinality of a minimal total dominating set in $G$. A comprehensive treatment of total domination is given in the 2013 book by Henning and Yeo [8].

1.2. Queens graphs on chessboards

A queens graph $Q_n$ is a graph whose vertices correspond 1-to-1 with the $n^2$ squares of an $n$-by-$n$ chessboard, and two squares are adjacent if and only if a queen on one square can move to the other square in one move, that is, the two squares lie on a common row, column, or diagonal. Notice that by definition the queens graph $Q_n$ applies only to $n$-by-$n$ square boards, as distinct from rectangular queens graphs $Q_{m,n}$ which apply to arbitrary $m$-by-$n$ chessboards. We should note that in the graph theory literature the notation $Q_n$ is also used to denote the $n$-dimensional cube graph. Since our entire focus in this note is on queens graphs, $Q_n$ will be reserved for these graphs.

The mathematical study of queens graphs dates back to the mid-to-late 1800s, most notably with the Eight Queens Problem of determining the maximum number of ways one can place 8 queens on a chessboard so that no two queens attack each other (lie on a common row, column, or diagonal), and the Five Queens Problem, of placing 5 queens on the board so that all unoccupied squares are attacked by at least one queen. The reader is referred to the 1892 book by W. W. Rouse Ball [1], and the 1908 book by H.E. Dudeney [4]. Two well-known solutions to the Five Queens Problem are shown in Figure 1.

Interested readers are also referred to two surveys of queens domination problems by Weakley [11], [12]. Other discussions of chessboard domination problems can be found in the 1964 book by Yaglom and Yaglom [13], which contains a comprehensive collection of results about independent, dominating, and independent dominating sets of a variety of chess pieces. In addition, the reader is referred to the 2004 book by Watkins [10] and a 2022 chapter by Hedetniemi and Hedetniemi [7].

2. Domatic numbers

The domatic number of a graph was introduced by Cockayne and Hedetniemi in 1975 [2] and subsequently studied by them in 1977 [3]. A domatic $k$-partition is a partition $\pi =\{V_1,V_2,\dots ,V_k\}$ of $V(G)$ into $k$ pairwise-disjoint dominating sets. Thus, the domatic number $dom(G)$ is the maximum order $k$ of a domatic $k$-partition. Note that many papers studying the domatic number use the notation $d(G)$. Here we use $dom(G)$ to avoid possible confusion with the use of $d$ to denote either distance in graphs, or the degree of a vertex in a graph, or the diameter of a graph.

To date approximately 280 papers have been published on various kinds of domatic numbers. We will mention only the following two variants here: (i) the idomatic number $idom(G)$ equals the maximum order of a partition of $V(G)$ into independent dominating sets, while the (ii) total domatic number $tdom(G)$ equals the maximum order of a partition of $V(G)$ into total dominating sets. Several survey papers and chapters have been written on various kinds of domatic numbers; see for example a chapter by Zelinka in 1998 [15] and a chapter by Goddard and Henning in 2021 [6].

The following basic results about the domatic number are worth mentioning.

In 1983 Zelinka [14] established the following lower bound on the domatic number of a graph.

In addition, one can show that for the complement $\overline{G}$ of a graph $G$, the following inequality holds.

3. Domatic numbers of queens graphs

In this paper we determine the value of $dom(Q_n)$ for $1\le n\le 6$ and $n=8$, and provide tight bounds for $n=7$ and $n=9$. In this regard, it will be helpful to note the following upper bounds provided by Theorem 2.1 as shown in Table 1. In this table we have a slight abuse of notation. In the upper bound of $n/\gamma (G)$, $n$ denotes the order of a graph $G$. In this case the order of $Q_n$ is actually $n^2$.

Table 1 $dom(Q_n)\le n^2/\gamma (Q_n)$

n	$dom(Q_n)$	$\le n^2/\gamma (Q_n)$
1	1	1/1 = 1
2	4	4/1 = 4
3	5	9/1 = 9
4	8	16/2 = 8
5	8	$\lfloor 25/3\rfloor =8$
6	10	36/3 = 12
7	11 or 12	$\lfloor 49/4\rfloor =12$
8	12	$\lfloor 64/5\rfloor =12$
9	12 or 13	$\lfloor 81/5\rfloor =16$

Since the entries in $Q_2$, $Q_4$, and $Q_5$ in Figure 2 meet the upper bounds, they are best possible, thereby establishing the facts that $dom(Q_2)=4$, $dom(Q_4)=8$ and $dom(Q_5)=8$. The fact that $dom(Q_3)=5$ follows from the observation that $\gamma (Q_3)=1$, but there is one unique dominating set of cardinality 1, the set consisting of the center square. All other dominating sets of a domatic partition of $Q_3$ will therefore have to have cardinality 2, and as can be seen there are four of them, the vertices, or squares, numbered 2, 3, 4, and 5, respectively. Thus, this solution is best possible.

The fact that $dom(Q_6)=10$ is shown in Figure 3. However, this solution does not meet the theoretical upper bound of 12. The reason begins with the observation that although $\gamma (Q_6)=3$, there is, up to isomorphism, only one unique dominating set of $Q_6$ of cardinality 3, as shown by the three queens in Figure 4.

This unique solution, however, requires the use of a corner square. Thus, through rotations, any domatic partition of $Q_6$ can have at most four dominating sets of cardinality 3. This leaves 36 – 12 = 24 squares yet to be covered, by dominating sets which must be of cardinality at least 4. Fortunately, the remaining uncovered 24 squares can be covered perfectly by six pairwise-disjoint dominating sets of cardinality 4, numbered 5, 6, 7, 8, 9, and 10, as shown in Figure 3.

The fact that $dom(Q_8)=12$ is shown in Figure 5. It is best possible since it achieves the proven upper bound of $\lfloor 64/5\rfloor =12$.

The situation for $dom(Q_7)$ is a bit more complex. There are $13$ minimum dominating sets of $Q_7$, each of cardinality $4$, such as the example shown in Figure 4. If 12 minimum dominating sets can be used, then $dom(Q_7)=\lfloor 49/4\rfloor =12$. The example given in Figure 6 establishes that $dom(Q_7)\ge 11$. Here we have used $8$ minimum dominating sets of cardinality $4$, and three minimal dominating sets, numbered $9,10,11$, of cardinality $5$. The two unnumbered squares can be assigned any number between 1 and 11.

The situation for $dom(Q_9)$ is also a bit more complex. There is, up to isomorphism, only one unique minimum dominating set of cardinality $5$, as shown in Figure 7.

But this set contains a queen on the central square. And therefore, in any domatic partition of $Q_9$, only one set can have cardinality $5$. Thus, $dom(Q_9)\le \lfloor 1+(81–5)/6\rfloor =13$. By adding an extra column to the left of the first column of $Q_8$ in Figure 5 and an extra row above the top row in Figure 5 we can produce a domatic 12-partition of $Q_9$ in which the entries in Figure 5 are unchanged, as shown in Figure 8. Thus, we can conclude that $12\le dom(Q_9)\le 13$.

4. Idomatic numbers of queens graphs

A graph $G=(V,E)$ is called idomatic if its vertex set can be partitioned into independent dominating sets. It is easy to see that not all graphs are idomatic, for example the cycle $C_5$ is not idomatic. The question then is: are all queens graphs idomatic? If a queens graph is idomatic, its idomatic number $idom(Q_n)$ is the maximum order of a partition of the vertices of $Q_n$ into independent dominating sets.

Figure 9 shows that $Q_2$ and $Q_3$ are idomatic, and Figure 10 shows that $Q_4$ is idomatic, as well. Since it is known that $i(Q_4)=3$, it follows that $idom(Q_4)\le \lfloor 16/3\rfloor =5$, which is achieved in Figure 10.

Figure 11 shows that $Q5$ and $Q_6$ are also idomatic.

The following Figure 13, found by a computer search, shows that $Q_8$ is idomatic. Since $\alpha (Q_8)=5$, it is possible that $Q_8$ can be partitioned into at most $\lfloor \frac{64}{5}\rfloor =12$ independent dominating sets. Thus, Figure 13 confirms that $idom(Q_8)=12$.

The following Table 2 summarizes what is known about idomatic queens graphs and their idomatic numbers. We have heard from Alice McRae [9] that her genetic algorithm has found an idomatic partition of $Q_9$ of order $11$.

Table 2 Idomatic queens graphs

n	idomatic?	$idom(Q_n)$
1	yes	1
2	yes	4
3	yes	5
4	yes	5
5	yes	7
6	yes	8
7	yes	10
8	yes	12
9	yes	$\ge 11$

5. Total domatic numbers of queens graphs

For the purposes of this paper, we will say that a graph $G=(V,E)$ is called domatic if its vertex set $V$ can be partitioned into minimal dominating sets. In determining the domatic number $dom(G)$ it does not matter if any of the sets $V_i$ in a $k$-domatic partition are minimal dominating sets, only that they are dominating sets. Thus, for the five-cycle $C_5$, $dom(C_5)=2$, but the vertices of $C_5$ cannot be partitioned into minimal dominating sets. Thus, $C_5$ is not a domatic graph.

Similarly, a graph $G=(V,E)$ is called total domatic if its vertex set $V$ can be partitioned into minimal total dominating sets. As with $C_5$, not all graphs are total domatic, for example, $C_5$ is also not total domatic, nor is $Q_3$, as can be seen by considering $Q_3$ as shown in Figure 2. For $Q_3$, ${\gamma }_t(Q_3)=2$, but $Q_3$ does not have a minimal total dominating set of cardinality $3$. As can be easily seen, the vertices of $Q_3$ can be partitioned into three minimum total dominating sets, each of cardinality $2$, and a fourth total dominating set of cardinality $3$, but this fourth set cannot be a minimal total dominating set. Thus, $Q_3$ is not total domatic. The following theorem, however, shows that except for for $n\ne 1,3$, all queens graphs $Q_n$ are both domatic and total domatic.

Theorem 5.1 shows that for $n\ge 4$, $n+2\le dom(Q_n)$ and $n+2\le tdom(Qn)$. This suggests the introduction of new parameters, which, in this case equal the minimum orders of a $k$-domatic, $k$-idomatic, and $k$-total domatic partition of a graph $G$. Figure 14 raises the following two questions: is it possible to partition $Q_n$ into fewer than $n+2$ minimal dominating sets or fewer than $n+2$ minimal total dominating sets? At the risk of abusing notation, and looking for a good notation, we could define $\underset{\_}{dom}(G)$ to equal the minimum order of a partition of $V(G)$ into minimal dominating sets, and $\overline{dom}(G)$ to equal the maximum order of a partition of $V(G)$ into minimal dominating sets. Thus, for queens graphs $\underset{\_}{dom}(Q_n)\le n+2\le \overline{dom}(Q_n)\le dom(Q_n)$, and similarly, $\underset{\_}{tdom}(G)\le n+2\le \overline{tdom}(Q_n)\le tdom(Q_n)$.

Table 3 provides the limited preliminary results for the total domatic numbers of the queens graphs, where for example, the paritition of $Q_4$ into a maximum possible eight minimum total dominating sets is shown in Figure 15.

Table 3 Total domatic numbers of $Q_n$

n	1	2	3	4	5	6	7	8
${\gamma }_t(Q_n)$	X	2	2	2	3	4	4	5
$tdom(Q_n)$	X	2	4	8	$8$	$9$	$11$	$12$

Figures 15 and  16 establish the total domatic numbers of $Q_2,Q_3,Q_4,Q_5,Q_6$.

A further analysis of the $22$ ${\gamma }_t$-sets of $Q_7$ given in the proof of Theorem 5.2 shows that, in fact, in any partition of $Q_7$ into a maximum number of total dominating sets, at most six ${\gamma }_t$-sets can appear, and the remaining five total dominating sets must have cardinality five, as shown in Figure 18. This can be seen by considering the graph $G_{22}$ of order $n=22$, whose vertices correspond 1-to-1 with the $22$ minimum total dominating sets of $Q_7$, and two vertices are adjacent if and only if the corresponding two minimum total dominating sets have a vertex in common. It can be seen that the vertex independence number of this intersection graph $G_{22}$ is six, that is, $\alpha (G_{22})=6$.

We conclude this section with the results of an exhaustive computer search which has found the following partition of $Q_8$, shown in Figure 19, into $12$ total dominating sets, eight of cardinality $5$ and four of cardinality $6$. A partition of $Q_8$ into $12$ total dominating sets is best possible since ${\gamma }_t(Q_8)=5$ and $\lfloor \frac{64}{5}\rfloor =12$. Thus, $tdom(Q_8)=12$.

6. Several new classes of domatic graphs

As shown in Figure 20, the vertices of $Q_5$ can, in fact, be partitioned into 5 maximum independent sets.

This raises the following concept. A graph $G$ is called $\alpha$-domatic if its vertices can be partitioned $\pi =\{V_1,V_2,\dots ,V_k\}$ into $k$ independent dominating sets such that for all $i\in [k]$, $|V_i|=\alpha (G)$, that is each set $V_i$ is in fact a maximum cardinality independent set. It is easy to see that all complete graphs $K_n$ are $\alpha$-domatic, as are all complete multipartite graphs of the form $K_{n_1,n_2,\dots ,n_k}$, where $n_1=n_2=\dots =n_k$. Since $Q_1\simeq K_1$, and $Q_2\simeq K_4$, it follows from Figures 9 and  20 that $Q_1$, $Q_2$, and $Q_5$ are all $\alpha$-domatic, but $Q_3$, $Q_4$, and $Q_6$ are not $\alpha$-domatic. This raises the question: which queens graphs $Q_n$ are $\alpha$-domatic? And, in general, which graphs $G$ are $\alpha$-domatic?

Similarly, one can define a graph $G$ of order $n$ to be:
if it has a vertex partition into $n/\gamma (G)$ minimum dominating sets,
if it has a vertex partition into $n/i(G)$ minimum independent dominating sets,
if it has a vertex partition into $n/\alpha (G)$ maximum independent sets,
if it has a vertex partition into $n/\mathrm{\Gamma }(G)$ maximum cardinality minimal dominating sets,
if it has a vertex partition into $n/{\gamma }_t(G)$ minimum total dominating sets,
if it has a vertex partition into $n/{\mathrm{\Gamma }}_t(G)$ maximum cardinality minimal total dominating sets.

7. Open problems and questions

1. Are all queens graphs $Q_n$ idomatic? In particular, are $Q_8$ and $Q_9$ idomatic?

2. Is the function $dom(Q_n)$ monotonic nondecreasing?

3. Is the function $idom(Q_n)$, when defined, monotonic nondecreasing?

4. What can you say about $\underset{\_}{dom}(Q_n)$ and $\overline{dom}(Q_n)$?

5. What can you say about $\underset{\_}{tdom}(Q_n)$ and $\overline{tdom}(Q_n)$?

6. What can you say about the values of $dom(Q_n)+dom(\overline{Q_n})$?

7. What are the values of $dom(Q_7)$ and $dom(Q_9)$?

8. What are the values of $tdom(Q_8)$ and $tdom(Q_9)$?

9. For $n\in \{10,11\}$, $\gamma (Q_n)=5$, and furthermore, there is up to isomorphism, only one unique dominating set in each of $Q_{10}$ and $Q_{11}$ of cardinality 5. This suggests that in a domatic partition of these two queens graphs, only four minimum dominating sets can appear, through rotations and/or reflections, and these will occupy 20 squares. All other dominating sets, therefore, will have to have cardinality of at least 6 and will occupy the remaining $n^2–20$ squares. This shows that the upper bounds for $dom(Q_n)$ for $n\in \{10,11\}$ are as follows:

   (i) $n=10$: $n^2=100$, $100–20=80$, and therefore $dom(Q_{10})\le \lfloor 4+80/6\rfloor =17$;

   (ii) $n=11$: $n^2=121$, $121–20=101$, and therefore, $dom(Q_{11})\le \lfloor 4+101/6\rfloor =20$.

10. For $n=12$, $\gamma (Q_{12})=6$, but there is up to isomorphism, only one unique minimum dominating set of cardinality $6$, and it uses a corner square. Thus, again, at most four minimum dominating sets can appear in any domatic partition of $Q_{12}$, which gives an upper bound for $Q_{12}$ of $dom(Q_{12})\le \lfloor 4+120/7\rfloor =21$.

11. Notice in Figures 15 and  16 that $Q_2$, $Q_4$ and $Q_6$ can all be partitioned precisely into minimum total dominating sets. Thus, $Q_2$, $Q_4$, and $Q_6$ are all ${\gamma }_t$-domatic.

    The final Table 5 summarizes what we have established about the domatic numbers, idomatic numbers, and total domatic numbers of queens graphs.

    Table 5 Known domatic, idomatic and total domatic numbers of queens graphs

    n	1	2	3	4	5	6	7	8	9
    $\gamma (Q_n)$	1	1	1	2	3	3	4	5	5
    $i(Q_n)$	1	1	1	3	3	4	4	5	5
    ${\gamma }_t(Q_n)$	X	2	2	2	3	4	4	5	6
    $dom(Q_n)$	1	4	5	8	8	10	11,12	12	12,13
    $idom(Q_n)$	1	4	5	5	7	8	10	$\le 12$	$\le 16$
    $tdom(Q_n)$	X	2	4	8	8	9	11	12	11-15

Declarations

The authors declare no conflict of interest.