Let \( G = (V, E) \) be a graph with vertex set \( V \) and edge set \( E \). A set \( S \subset V \) is a dominating set if every vertex in \( V – S \) is adjacent to at least one vertex in \( S \), an independent set if no two vertices in \( S \) are adjacent, and a total dominating set if every vertex in \( V \) is adjacent to at least one vertex in \( S \). The domatic number \( \text{dom}(G) \), idomatic number \( \text{idom}(G) \), and total domatic number \( \text{tdom}(G) \), of a graph \( G \) equal the maximum order \( k \) of a partition \( \pi = \{V_1, V_2, \ldots, V_k\} \) of \( V \) into {dominating sets, independent dominating sets, total dominating sets}, respectively. A queens graph \( Q_n \) is a graph defined on the \( n^2 \) squares of an \( n \)-by-\( n \) chessboard, such that 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. In this note, we determine the value of these three numbers for \( Q_n \) for the first several values of \( n \). In addition, we introduce the concepts of graphs being \( \gamma \)-domatic, \( i \)-domatic, \( \alpha \)-domatic, \( \Gamma \)-domatic, \( \gamma_t \)-domatic, and \( \Gamma_t \)-domatic.
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\).
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 \(\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 \(\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].
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].
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, \ldots, 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.
In this paper we determine the value of \(dom(Q_n)\) for \(1 \le n \leq 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\).
| 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\).
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.
Proof. Let \(\pi = \{V_1, V_2, \ldots, V_k\}\) be a maximum order partition of \(Q_5\) into independent dominating sets. It is well-known that \(i(Q_5) = 3\) and \(\alpha(Q_5) = 5\). Thus, for \(1 \le i \le k\), \(3 \le |V_i| \le 5\). In any idomatic partition of \(Q_5\) the center square must appear in exactly one set. We can assume without loss of generality that the center square appears in set \(V_1\). It can be shown by enumeration that, subject to rotations and reflections, there is only one independent dominating set of \(Q_5\) that contains the center square, and it has cardinality 5; it consists of the center square and four squares on the outermost columns and rows, each symmetrically adjacent to a corner square, as shown in Figure 11, where these five squares in \(Q_5\) are numbered 4. Thus, we can assume that \(|V_1| = 5\). The remaining 25 – 5 = 20 squares are in independent dominating sets of cardinality 3 or 4. Thus, there can be at most 6 other independent dominating sets, and hence, \(idom(Q_5) \le 7\). The solution in Figure 11, which was found by computer search, shows that 7 is achievable. ◻
Proof. It is well known that \(i(Q_6) = 4\), and thus, in theory, \(Q_6\) could be partitioned into 9 independent dominating sets of cardinality 4. It is known that up to isomorphism there are 17 minimum independent dominating sets of cardinality 4 in \(Q_6\). Computer search, however, shows that no collection of 9 minimum independent dominating sets can partition the vertices of \(Q_6\), while 948 idomatic partitions of \(Q_6\) of order 8 exist, such as that shown in Figure 11. Thus, \(idom(Q_6) = 8\). ◻
Proof. Figure 12 shows an idomatic partition of \(Q_7\) of order 10, which has one independent dominating set of minimum cardinality 4 (numbered 1 in Figure 12) and nine independent dominating sets of cardinality 5; therefore \(Q_7\) is idomatic. Since it is known that \(i(Q_7) = 4\), it follows that \(10 \le idom(Q_7) \le \lfloor 49/4 \rfloor = 12\).
But \(idom(Q_7) < 11\) for the following reason. It is known not only that \(i(Q_7) = 4\), but there is only one minimum independent dominating set of \(Q_7\) up to isomorphism, and every reflection or rotation of this one set uses a middle square in an outer row or column; notice the square numbered one in the middle of the bottom row of Figure 12. There are only four such squares.
Thus, we can use up at most 4 x 4 squares with independent dominating sets of cardinality 4. All other independent dominating sets must have cardinality 5, 6, or 7, and this must fill up the remaining 49 – 16 = 33 squares. However, there can be at most \(\lfloor 33/5 \rfloor = 6\) such sets, thus allowing at most 4 + 6 = 10 disjoint independent dominating sets. Thus, \(idom(Q_7) = 10\). ◻
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\).
| 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\) |
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.
Proof. For \(n \ge 4\), define the following partition of the vertices of \(Q_n\) of order \(n + 2\), \(\pi = \{V_{c1}, V_{r1}, V_{cn},\\ V_{rn}, V_2, \ldots, V_{n-1}\}\), as follows: (i) \(V_{c1}\) contains all \(n-1\) squares in the first (leftmost column) excluding the top-left corner square, (ii) \(V_{r1}\) contains the leftmost \(n-1\) squares in the top-row, excluding the top-right corner square, (iii) \(V_{cn}\) contains the topmost \(n-1\) squares in the rightmost column, excluding the bottom-right corner square, (iv) \(V_{rn}\) contains the \(n-1\) rightmost squares in the bottom row, excluding the leftmost corner square. Each of the \(n-2\) sets \(V_2, \ldots, V_{n-1}\) contain the \(n-2\) squares in a middle column between the topmost and bottommost squares of that column, as shown in Figure 14.
It is easy to see that each of these \(n+2\) sets is both a minimal dominating set and a minimal total dominating set, since in each set, every queen has several external private neighbors, that is, squares it attacks that no other queen of the same color attacks. ◻
Theorem 5.1 shows that for \(n \ge 4\), \(n+2 \le dom(Q_n)\) and \(n+2 \leq 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 \(\underline{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 \(\underline{dom}(Q_n) \le n+2 \le \overline{dom}(Q_n) \le dom(Q_n)\), and similarly, \(\underline{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.
| 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\).
Proof. Let the squares of the queens graph \(Q_7\) be numbered as in Figure 17.
A computer program has shown that \(\gamma_t(Q_7) = 4\) and there are precisely \(22\) minimum total dominating sets. One can partition these \(22\) \(\gamma_t\)-sets into six groups as in Table 4, where the \(\gamma_t\)-sets in Groups II through VI are the four \(\gamma_t\)-sets obtained by rotations of one \(\gamma_t\)-set.
| Group I | Group II | Group III |
| {1, 19, 31, 49} | {1, 9, 27, 39} | {2, 8, 27, 45} |
| {7, 17, 33, 43} | {7, 13, 23, 39} | {6, 14, 15, 39} |
| {11, 23, 41, 49} | {5, 23, 42, 48} | |
| {11, 27, 37, 43} | {11, 35, 36, 44} | |
| Group IV | Group V | Group VI |
| {6, 14, 23, 47} | {4, 25, 32, 39} | {13, 19, 25, 37} |
| {11, 29, 42, 48} | {23, 24, 25, 28} | {9, 25, 33, 41} |
| {3, 27, 36, 44} | {11, 18, 25, 46} | {13, 25, 31, 37} |
| {2, 8, 21, 39} | {22, 25, 26, 27} | {9, 17, 25, 41} |
One can see that eight of the \(49\) squares of \(Q_7\) never appear in a \(\gamma_t\)-set; they are the squares numbered \(10, 12, 16, 20, 30, 34, 38, 40\). Thus, only \(41\) squares can be used in a partition of \(Q_7\) into \(\gamma_t\)-sets. Therefore, in a maximum order partition of \(Q_7\) into total dominating sets there can be at most \(10\) sets of cardinality \(4\) and only one other set of cardinality \(5\) or greater.
Figure 18 shows a partition of \(Q_7\) into \(11\) minimal total dominating sets. Therefore, \(tdom(Q_7) = 11\). ◻
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\).
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, \ldots, 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, \ldots, n_k}\), where \(n_1 = n_2 = \ldots = 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/
\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/\Gamma_t(G)\) maximum cardinality minimal
total dominating sets.
Are all queens graphs \(Q_n\) idomatic? In particular, are \(Q_8\) and \(Q_9\) idomatic?
Is the function \(dom(Q_n)\) monotonic nondecreasing?
Is the function \(idom(Q_n)\), when defined, monotonic nondecreasing?
What can you say about \(\underline{dom}(Q_n)\) and \(\overline{dom}(Q_n)\)?
What can you say about \(\underline{tdom}(Q_n)\) and \(\overline{tdom}(Q_n)\)?
What can you say about the values of \(dom(Q_n) + dom(\overline{Q_n})\)?
What are the values of \(dom(Q_7)\) and \(dom(Q_9)\)?
What are the values of \(tdom(Q_8)\) and \(tdom(Q_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\).
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\).
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.
| 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 |
The authors declare no conflict of interest.
1970-2025 CP (Manitoba, Canada) unless otherwise stated.