An alternative proof of A.B. Evans’ result on the existence of strong complete mappings on finite abelian groups is presented. Applications of strong complete mappings in computing the chromatic numbers of~certain Cayley graphs are discussed.
In [1], for every group \(G\), we defined a family of graphs \(\mathscr{G}_m(G)\), indexed by positive integers \(m\). Our motivation for studying these graphs originated from certain questions in ring theory. However, it turned out that these graphs possess sufficiently interesting properties to warrant independent investigation.
The graph \(\mathscr{G}_m(G)\) is the Cayley graph \(\it{Cay}(G^m,S(m))\), whose set of vertices is the Cartesian power \(G^m\) and \[\label{S(m)} \mathcal{S}(m)=\{\mathbf{x}_{[k,l)}: x\in G^{*}, 1\leqslant k<l\leqslant m+1 \}, \tag{1}\] where \[\label{x[kl]} \mathbf{x}_{[k,l)}=(\underbrace{e,e,\dots,e}_{k-1 \ \ {\rm times }},\underbrace{x,x,\dots,x}_{l-k \ \ {\rm times }},\underbrace{e,e,\dots,e}_{m-l+1\ \ {\rm times }}) \ \ \text{and} \ \ G^{*}=G\setminus\{e\}. \tag{2}\]
In other words, the vertices of \(\mathscr{G}_m(G)\) are the elements of \(G^m\) and two \(m\)-tuples \(\mathbf{g}\) and \(\mathbf{h}\) are declared to be adjacent if there exists some \(\mathbf{x}\in \mathcal{S}(m)\) with \(\mathbf{g}=\mathbf{x}\cdot\mathbf{h}\).
It is proved in [1] that any member of our family of graphs determines the group \(G\), in the sense that for the given integer \(m>1\) and groups \(G\), \(H\) such that the graphs \(\mathscr{G}_m(G)\) and \(\mathscr{G}_m(H)\) are isomorphic, \(G\) and \(H\) are isomorphic as well.
Let \(G\) be a finite group. A bijection \(\sigma\colon G\to G\) is called a complete mapping if the map \(x\mapsto x\sigma(x)\) is also a bijection. The question of which finite groups admit a complete mappings has been investigated in numerous papers. According to the results of Hall and Paige [8], Wilcox [11], Evans [4], and Bray et al. [2], a finite group \(G\) admits a complete mapping if and only if its Sylow \(2\)-subgroups are not cyclic of order greater than \(1.\) These results, along with the connection between groups admitting complete mappings and the problem of the existence of orthogonal latin squares, can be found in Evans’ book [6].
In this paper, we investigate the finite groups \(G\) for which the graphs \(\mathscr{G}_2(G)\) and \(\mathscr{G}_3(G)\) satisfy the property that their chromatic number equals their clique number (Section 3). It follows from [6, Theorem 1.12 ad Theorem 1.15], that a group \(G\) admits a complete mapping if and only if the chromatic number of the latin square based on the group \(G\) equals \(|G|\). We demonstrate (Proposition 3.1) that this is equivalent to the chromatic number of \(\mathscr{G}_2(G)\) being \(|G|\).
The main goal of this paper is to establish a connection between the chromatic number of \(\mathscr{G}_3(G)\) and the groups admitting strong complete mappings, for \(G\) abelian.
Recall that for a finite group \(G\), a bijection \(\sigma\colon G\to G\) is called a strong complete mapping if both maps \[x\mapsto x\sigma(x)\ \ \text{ and }\ \ x\mapsto x^{-1}\sigma(x),\] are bijections.
Finite abelian groups that admit strong complete mappings were characterized by Evans [5, Theorem 15]. He proved that a finite abelian group admits strong complete mappings if and only if neither its Sylow \(2\)-subgroup nor its Sylow \(3\)-subgroup is nontrivial and cyclic. The essential and most challenging step in Evans’ proof was demonstrating the existence of a strong complete mapping in the direct product \(\mathbb{Z}_3\times \mathbb{Z}_{3^n}\). In Section 2 we present an alternative construction of a strong complete mapping \(\sigma\) for this group. In our approach we split the group into several subsets and \(\sigma\) acts on them as affine functions with precisely defined parameters specific to each subset, which are independent of \(n\).
Recall that the clique number of a graph is the order of the maximum clique (a clique with the largest possible number of vertices). In [1, Proposition 4.7] it is proved that the clique number \(\omega\) of the graph \(\mathscr{G}_m(G)\), is equal to \[\label{clique_number} \omega = \left\{\begin{array}{cl} {\rm max}\{m+1, |G|\} & {\rm if}\ \ (m,|G|)\neq (2,2),\\ 4 & {\rm if}\ \ (m,|G|)= (2,2).\\ \end{array}\right. \tag{3}\]
In particular, for \(m=3\) and \(|G| > 3\), we have \(\omega = |G|\).
We recall that the chromatic number \(\chi\) of a graph is the lowest number of colours required to colour the vertices of graph such that no two adjacent vertices share the same colour (proper colouring). Vertices within each clique must have different colours. It implies that the chromatic number must be greater or equal to the clique number.
For technical reasons, we will introduce a modification of the concept of a strong complete mapping. A complete mapping \(\sigma\colon G\to G\) will be called a double complete mapping if \(\delta_1\colon G\to G\) defined by \(\delta_1(x) =x\sigma(x)\) is a complete mapping. This implies that \(\delta_2(x)=x^2\sigma(x)\) is a bijection. Thus, \(\sigma\) is a double complete mapping on \(G\) if and only if \(\delta_1\) is a strong complete mapping.
The following lemma is rather well-known. We include it with a proof sketch for the sake of completeness.
Lemma 2.1. If \(H\) is a subgroup of an abelian group \(G\) such that both \(H\) and \(G/H\) admit double complete mappings, then the group \(G\) admits a double complete mapping.
Proof. (sketch) Let \(\eta:H\to H\) and \(\theta\colon G/H \to G/H\) be double complete mappings. Let \(\{x_1=e, x_2,\ldots, x_m\}\) denote a set of representatives of the cosets with respect to \(H\) and let \(\tau\colon\{1,2,\ldots,m\}\to \{1,2,\ldots,m\}\) be a bijection such that \(\theta(Hx_i)=Hx_{\tau(i)}\).
Every element \(g\in G\) has a unique decomposition \(g=h_gx_i\), where \(h_g\in H\) and \(1\leqslant i\leqslant m\). Define a mapping \(\sigma\colon G\to G\) by the formula \[\sigma (g)=\eta(h_g)x_{\tau(i)}.\]
Then, it can be easily verified that \(\sigma\) is a double complete mapping. ◻
Now we present an alternative proof of the key lemma for the existence of a double complete mapping for abelian \(3\)-groups. The constructed function has a rather elegant form, and the proof that it satisfies the required conditions for being a double complete mapping is relatively straightforward. Nevertheless, finding it required a significant effort from the authors.
Lemma 2.2. Let \(n\geqslant 4\) and \(m=3^{n-1}\). The mapping \(\sigma\colon \mathbb{Z}_3\times\mathbb{Z}_{3m}\to \mathbb{Z}_3\times\mathbb{Z}_{3m}\) such that \[\sigma(i,k)=\left\{\begin{array}{ll} (a_k,3k), & \text{ if } i=0,\\ (b_k,3k-80), & \text{ if } i=1,\\ (c_k,3k-40), & \text{ if } i=2,\\ \end{array} \right.\] where
\[\begin{aligned} a_k=&\left\{\begin{array}{ll} 0, & \text{ if } 0\leqslant k< m ,\\ 1, & \text{ if } m \leqslant k< 2m,\\ 2, & \text{ if } 2m\leqslant k<3m, \end{array} \right.\\ b_k=&\left\{\begin{array}{ll} 0, & \text{ if } 18\leqslant k\leqslant m+17,\\ 1, & \text{ if } m+18\leqslant k\leqslant 2m +17,\\ 2, & \text{ if } 2m+18\leqslant k<3m \text{ or } 0\leqslant k\leqslant 17, \end{array} \right.\\ c_k=&\left\{\begin{array}{ll} 0, & \text{ if } 10\leqslant k\leqslant m+7 \text{ or } k\in\{2m+8,2m+9\},\\ 1, & \text{ if } k\in\{8,9\} \text{ or } m+10\leqslant k\leqslant 2m+7,\\ 2, & \text{ if } 0\leqslant k\leqslant 7 \text{ or } k\in\{ m+8, m+9\} \text{ or } 2m+10\leqslant k< 3m, \end{array} \right. \end{aligned}\] is a double complete mapping.
Proof. We need to prove that the mappings \(\delta_1, \delta_2\colon \mathbb{Z}_3\times\mathbb{Z}_{3m}\to \mathbb{Z}_3\times\mathbb{Z}_{3m}\) given by
\[\delta_1(i,k)=\left\{\begin{array}{ll} (a_k,4k) & \text{ if } i=0,\\ (b_k+1,4k-80) & \text{ if } i=1,\\ (c_k+2,4k-40) & \text{ if } i=2,\\ \end{array} \right. \hspace{5mm} \delta_2(i,k)=\left\{\begin{array}{ll} (a_k,5k) & \text{ if } i=0,\\ (b_k+2,5k-80) & \text{ if } i=1,\\ (c_k+1,5k-40) & \text{ if } i=2 ,\\ \end{array} \right.\] are bijections.
For each \(i=0,1,2\), we define define three sets based on sequences \(a_k\), \(b_k\), \(c_k\): \[A_i=\{ k\mid a_k=i\},\ \ \ B_i=\{ k\mid b_k=i\},\ \ \ C_i=\{ k\mid c_k=i\}.\]
For \(a,b\in \mathbb{Z}\), \(a\leqslant b\), the set \(\{a,a+1,\ldots,b\}\) we denote by \([ a,\, b]\). Moreover, for subsets \(X,Y\subseteq \mathbb{Z}\) the set \(X-Y\) of differences is defined as: \[\{x-y\mid x\in X, y\in Y\}.\]
The following graphic will be helpful for the easy identification of the sets \(A_i\), \(B_i\) and \(C_i\), where \(i=1,2,3\).
Suppose, for the sake of contradiction, that either \(\delta_1\) or \(\delta_2\) is not a bijection. To analyze this assumption, we consider six cases:
1. \(\delta_1(0,k)=\delta_1(1,l)\) for some \(k,l\in \mathbb{Z}_{3m}\).
In this case, we have \(a_k=b_l+1\) and \(4k=4l-80\). Thus, \(l-k=20\), since \(4\) is an invertible element in \(\mathbb{Z}_{3m}\), and hence \(a_k=b_{k+20}+1\).
Now, if \(a_k=0\), then \(b_{k+20}=2\). Thus, by definition of the sets \(A_i\), \(B_i\) and \(C_i\), \(k\in A_0\) and \(k+20\in B_2\). Similarly, if \(a_k=1\), then \(b_{k+20}=0\), that is \(k\in A_1\) and \(k+20\in B_0\). Finally, if \(a_k=2\), then \(b_{k+20}=1\), that is \(k\in A_2\) and \(k+20\in B_1\). Therefore \[20\in (B_2-A_0)\cup (B_0-A_1)\cup (B_1-A_2).\]
But this is not true, as by Figure 1, \[\begin{array}{rcl} B_2-A_0&=& ([0,\, 17]\cup [2m+18,\, 3m-1]) – [ 0,\, m-1 ]\\ &=&[-m+1,\,17]\cup [m+19,\, 3m-1], \\ B_0-A_1 &=& [18,\,m+17]-[m,\,2m-1]= [-2m+19,\,17], \\ B_1-A_2&=& [m+18,\,2m+17]-[2m,\,3m-1]=[-2m+19,\, 17]. \end{array}\]
The remaining cases are proved analogously.
2. \(\delta_1(0,k)=\delta_1(2,l)\) for some \(k,l\in \mathbb{Z}_{3m}\).
In this case \(a_k=c_l+2\) and then \(4k=4l-40\). Thus, \(l=k+10\), and \(a_k=c_{k+10}+2\). By analyzing the cases \(a_k=0\), \(a_k=1\) and \(a_k=2\) consecutively, we obtain \(c_{k+10}=1\), \(c_{k+10}=2\), and \(c_{k+10}=0\), respectively. This implies that if \(k\in A_0\), then \(k+10\in C_1\), if \(k\in A_1\), then \(k+10\in C_2\), and finally, if \(k\in A_2\), then \(k+10\in C_0\). Therefore \[\label{punkt2} 10\in (C_1-A_0)\cup (C_2-A_1)\cup (C_0-A_2).\]
But by the above graphic \[\begin{array}{rcl} C_1-A_0&=& ([m+10,\, 2m+7]\cup [8,\, 9]) – [ 0,\, m-1 ]\\ &=& [11,\,2m+7]\cup [-m+9,\, 9], \\ C_2-A_1&=& [0,7]\cup [m+8,\,m+9]-[2m+10,\,3m-1]\\ &=& [-2m+1,\,7-m]\cup [-m+9,\,9]\cup [m+10,\,2m-1], \\ C_0-A_2&=& ([10,\,m+7]\cup [2m+8,\,2m+9])-[2m,\,3m-1]\\ &=& [-3m+11,\,-m + 7]\cup [-m+9,\,9]. \end{array}\]
So, none of the components of the union contains the number \(10\).
3. \(\delta_1(1,k)=\delta_1(2,l)\) for some \(k,l\in \mathbb{Z}_{3m}\).
In this case, we have \(b_k+1=c_l+2\) and \(4k-80=4l-40\). Thus, \(k=l+10\), and \(b_{l+10}=c_{l}+1\). So analogously, as in the previous cases we have to verify whether \(10\) belongs to the union of the sets \(B_1-C_0\), \(B_2-C_1\) and \(B_0-C_2\). Again, using Figure 1, one can easily check that it is not true, as
\[\begin{aligned} B_1-C_0=& [m+18,\, 2m+17] – ([10,\, m+7] \cup [2m+8,\, 2m+9])\\ =& [11,\, 2m+7]\cup [-m+9,\, 9], \\ B_2-C_1=& ([0,\, 17]\cup [2m+18,\, 3m-1])-([m+10,\, 2m+7]\cup [8,\, 9])\\ =& [-2m-7,\, -m+7]\cup [-9,\,9]\cup [11,\, 2m-11]\cup [2m+9,\, 3m-9], \\ B_0-C_2=& [18,\,m+17]-([0,\,7]\cup [m+8,m-9]\cup [2m+10,\, 3m-1])\\ =& [11,\, m+17]\cup [-m+9,\, 9]\cup [-3m+17,\,-m+7]. \end{aligned}\]
Consequently, the equality \(b_{l+10}=c_{l}+1\) does not hold.
We have thus proven that \(\delta_1\) is a bijection. Now we will prove that \(\delta_2\) is also a bijection.
4. \(\delta_2(0,k)=\delta_2(1,l)\) for some \(k,l\in \mathbb{Z}_{3m}\).
In this case \(a_k=b_l+2\) and \(5k=5l-80\). Thus, since \(5\) is an invertible element in \(\mathbb{Z}_{3m}\), \(l=k+16\), and hence \(a_{k}=b_{k+16}+2\). Analogously, as in the previous cases we need to consider the sets \[\begin{array}{rcl} B_0-A_2&=& [18,\,m+ 17] – [2m,\, 3m-1] =[ -3m+19,\, -m+17], \\ B_1-A_0&=& [m+18,\,2m+17]-[0,\,m-1]= [19,\,2m +17], \\ B_2-A_1&=& ([0,\,17]\cup [2m+18,\,3m-1])- [m,\,2m-1]\\ &=& [-2m+1,\,-m+17]\cup [19,\,2m-1]. \end{array}\]
It is seen that none of them contains \(16\), so the equality \(a_{k}=b_{k+16}+2\) does not hold.
5. \(\delta_2(0,k)=\delta_2(2,l)\) for some \(k,l\in \mathbb{Z}_{3m}\).
In this case \(a_k=c_l+1\) and \(5k=5l-40\). Thus, \(l=k+8\), and hence \(a_{k}=c_{k+8}+1\). This is true, when \(8\) belongs to at least one of the sets\[\begin{array}{rcl} C_0-A_1&=& ([10,\, m+7]\cup [2m+8,\, 2m+9]) – [ m,\, 2m-1 ]\\ &=& [-2m+1,\,7]\cup [9,\,m+9], \\ C_1-A_2&=& ([m+10,\, 2m+7]\cup [8,\,9]) -[2m,\,3m-1]\\ &=& [-2m+11,\,7]\cup [-3m+9,\, -2m+9], \\ C_2-A_0&=& ([0,\, 7]\cup [m+8,\,m+9]\cup [2m+10,\, 3m-1])-[0,\,m-1]\\ &=& [-m+1,\, 7]\cup [9,\, m+9]\cup [m+11,\, 3m-1]. \end{array}\]
It is seen that it is not the case, therefore, the equality \(a_{k}=c_{k+8}+1\) does not hold.
6. \(\delta_2(1,k)=\delta_2(2,l)\) for some \(k,l\in \mathbb{Z}_{3m}\).
In this case \(b_k+2=c_l+1\) and \(5k-80=5l-40\). Thus, \(k=l+8\), and hence \(b_{l+8}=c_{l}+2\). Again, we have to verify whether \(8\) is an element of at least one of the sets \[\begin{array}{rcl} B_0-C_1&=& [18,\,m+17] – ([m+10,\, 2m+7]\cup [8,\,9])\\ &=& [-2m+11,\,7]\cup [9,\, m+9], \\ B_1-C_2&=& [m+18,\,2m+17]-([0,7]\cup[m+8,\,m+9]\cup [2m+10,\,3m-1])\\ &=& [m+11,\,2m+17]\cup [9.\, m+9] \cup [-2m+19,\, 7], \\ B_2-C_0&=& ([0,\,17]\cup [2m+18,\,3m-1])-(10,\,m+7]\cup [2m+8,\, 2m+9])\\ &=& [-m-7,\, 7]\cup [-2m-9,\,-2m+8]\cup [m+11,3m-11]\cup [9,\,m-9]. \end{array}\]
Again, it is no the case, so the equality \(b_{l+8}=c_{l}+2\) does not hold.
Since each case leads to a contradiction, we conclude that both \(\delta_1\) and \(\delta_2\) must be bijections. ◻
Remark 2.3. A reduction modulo \(9\) and \(27\) of the mappings from Lemma 2.2 gives the appropriate double complete mappings for the groups \(\mathbb{Z}_3\times \mathbb{Z}_{9}\) and \(\mathbb{Z}_3\times \mathbb{Z}_{27}\). Specifically, \[\sigma(i,k)=\left\{\begin{array}{ll} (a_k,3k), & \text{ if } i=0,\\ (b_k,3k+1), & \text{ if } i=1,\\ (c_k,3k+5), & \text{ if } i=2,\\ \end{array} \right.\] where \[\begin{aligned} a_k=&\left\{\begin{array}{ll} 0, & \text{ if } 0\leqslant k\leqslant 2 ,\\ 1, & \text{ if } 3 \leqslant k\leqslant 5,\\ 2, & \text{ if } 6\leqslant k\leqslant 8, \end{array} \right. \\ b_k=&\left\{\begin{array}{ll} 0, & \text{ if } 0\leqslant k\leqslant 2,\\ 1, & \text{ if } 3 \leqslant k\leqslant 5,\\ 2, & \text{ if } 6\leqslant k\leqslant 8,\\ \end{array} \right.\\ c_k=&\left\{\begin{array}{ll} 0, & \text{ if } k\in\{1,5,6\},\\ 1, & \text{ if } k\in\{0,4,8\} ,\\ 2, & \text{ if } k\in\{2,3,7\}, \\ \end{array} \right. \end{aligned}\] is a double complete mapping for \(\mathbb{Z}_3\times \mathbb{Z}_{9}\), and
\[\sigma(i,k)=\left\{\begin{array}{ll} (a_k,3k), & \text{ if } i=0,\\ (b_k,3k+1), & \text{ if } i=1,\\ (c_k,3k+14), & \text{ if } i=2, \end{array} \right.\] where \[\begin{aligned} a_k=&\left\{\begin{array}{ll} 0, & \text{ if } 0\leqslant k\leqslant 8 ,\\ 1, & \text{ if } 9 \leqslant k\leqslant 17,\\ 2, & \text{ if } 18\leqslant k\leqslant 26, \end{array} \right. \\ b_k=&\left\{\begin{array}{ll} 0, & \text{ if } 18\leqslant k\leqslant 26,\\ 1, & \text{ if } 0\leqslant k\leqslant 8,\\ 2, & \text{ if } 9\leqslant k\leqslant 17, \end{array} \right.\\ c_k=&\left\{\begin{array}{ll} 0, & \text{ if } k\in\{0,26\} \text{ or } 10\leqslant k\leqslant 16,\\ 1, & \text{ if } k\in\{8,9\} \text{ or } 19\leqslant k\leqslant 25 ,\\ 2, & \text{ if } k\in\{17,18\} \text{ or } 1\leqslant k\leqslant 7 ,\\ \end{array} \right. \end{aligned}\] is a double complete mapping for \(\mathbb{Z}_3\times \mathbb{Z}_{27}\).
In [3] and [9] it is proven that noncylic abelian \(2\)-groups admit strong complete mappings. Moreover, for \(n\geqslant 2\) the group \((\mathbb{Z}_3)^n\) can be viewed as an additive subgroup of the \(3^n\)-element field \(\mathbb{F}_{3^n}\). The mapping \(x\mapsto \xi x\), where \(\xi\) does not belong to the simple subfield of \(\mathbb{F}_{3^n}\) is a strong complete mapping. Consequently, by Lemmas 2.1 and 2.2 we deduce (via induction on the order of a group) that noncylic abelian \(3\)-groups admit strong complete mappings.
Theorem 2.4. [5, Theorem 15] A finite abelian group admits strong complete mappings (equivalently, double complete mappings) if and only if neither its Sylow \(2\)-subgroup nor its Sylow \(3\)-subgroup is nontrivial and cyclic.
Proof. Let \(G=A\oplus B\oplus C\), where \(A\) is the Sylow \(2\)-subgroup, \(B\) is the Sylow \(3\)-subgroup of \(G\) and \(C\) is the remaining direct summand. By the above consideration, each nontrivial subgroups among of \(A\) and \(B\) admits strong complete mappings. If \(C\) is nontrivial, then any of its elements has order greater than \(3\). Hence the identity map on \(C\) is a strong complete mapping. By Lemma 2.1, the group \(G\) admits a strong complete mapping. ◻
In this section we will discuss the relationship between the
existence of complete mappings and double complete mappings and the
chromatic numbers of graphs \(\mathscr{G}_2(G)\) and \(\mathscr{G}_3(G)\).
* By (1) we have \[\begin{array}{rcl}
\mathcal{S}(2)&=&(G^*\times\{e\})\cup (\{e\}\times G^*) \cup
\{(x,x)\mid x\in G^*\},\\[6pt]
\mathcal{S}(3)&=&(G^*\times\{e\}\times\{e\})\cup (\{e\}\times
G^*\times\{e\})
\cup(\{e\}\times \{e\}\times G^*)\cup\\[4pt]
&& \{(x,x,e)\mid x\in G^*\}\cup \{(e,x,x)\mid x\in G^*\}
\cup \{(x,x,x)\mid x\in G^*\}.
\end{array}\]
Proposition 3.1. The chromatic number of the graph \(\mathscr{G}_2(G)\) is equal to \(|G|\) if and only if the group \(G\) admits a complete mapping.
Proof. Suppose that the chromatic number of the graph \(\mathscr{G}_2(G)\) is equal to the order of the group \(G\). Let \(C\) be the colour assigned to the vertex \((e,e)\). For any element \(x\in G^*\) consider the set \(V_x=\{(gx,g)\mid g\in G\}\). The set \(V_x\) forms a clique of maximal size in the graph \(\mathscr{G}_2(G)\) and thus there must be a vertex \((\tau(x)x,\tau(x))\) in \(\mathscr{G}_2(G)\) that has the same colour \(C\). Note that \(\tau(x)\neq e\). Indeed, the vertices \((e,e)\) and \((x,e)\) are connected in \(\mathscr{G}_2(G)\), so they cannot share the same colour.
For any \(x,y\in G\) the vertices \((\tau(x)x,\tau(x))\) and \((\tau(y)y,\tau(x)),\) are adjacent in the graph \(\mathscr{G}_2(G)\), so if \(x\neq y\), then \(\tau(x)\neq \tau(y)\). Furthermore, the vertices \((\tau(x)x,\tau(x))\) and \((\tau(x)x,\tau(y))\) are also adjacent in \(\mathscr{G}_2(G)\), so \(\tau(x)x\neq \tau(y)y\), provided \(x\neq y\). Thus, the mappings \(x\mapsto \tau(x)\) and \(x\mapsto \tau(x)x\) are bijections. Consequently, \(\sigma=\tau^{-1}\) is a complete mapping.
Now suppose that \(G\) admits a complete mapping \(\sigma\). Then \(\tau=\sigma^{-1}\) is a bijection such that the map \(x \mapsto \tau(x)x\) is a bijection. We define the map \(c\colon G \times G \to G\) by \[c(x,y)=\tau(x)y.\]
We claim that this map \(c\) is a colouring function for the graph \(\mathscr{G}_2(G)\). To establish this, we need to prove that for any \(s \in G\), each of the following conditions imply that \(s = e\):
\(c(sx,y)=c(x,y)\);
\(c(x,sy)=c(x,y)\);
\(c(sx,sy)=c(x,y)\).
In the first case, we have \(\tau(sx)y=\tau(x)y\). This implies \(\tau(sx)=\tau(x)\), and therefore \(s=e\). In the second case, we obtain \(\tau(x)sy=\tau(x)y\), which clearly leads to \(s=e\). In the final case we get \(\tau(sx)sy=\tau(x)y\). Then \(\tau(sx)s=\tau(x)\), and hence \(\tau(sx)sx=\tau(x)x\). Since the mapping \(x\mapsto \tau(x)x\) is a bijection, we obtain \(s=e\). Therefore, the function \(c(x, y) = \tau(x)y\) defines a proper colouring for the graph \(\mathscr{G}_2(G)\). ◻
The Hall-Paige conjecture was ultimately confirmed in [2], which allows us to formulate the following theorem:
Theorem 3.2. If \(G\) is a finite group, then \(\chi(\mathscr{G}_2(G))=|G|\) if and only if the Sylow \(2\)-subgroups of \(G\) are either trivial or non-cyclic.
Now we will investigate the chromatic number of the graph \(\mathscr{G}_3(G)\), where \(G\) is a finite abelian group.
Proposition 3.3. If \(G\) is a finite abelian group, such that \(G\) admits a double complete mapping, then \(\chi(\mathscr{G}_3(G))=|G|\).
Proof. Let \(\sigma\colon G\to G\) be a bijection such that both \(x\mapsto x\sigma(x)\) and \(x\mapsto x^2\sigma(x)\) are bijections. A colouring map \(c\colon G^3 \to G\) we define as follows \[c(x,y,z)=x\sigma(y)z,\] where \(x,y,z\in G\). It must be proven that the function \(c\) takes different values for pairs of vertices connected by an edge in the graph \(\mathscr{G}_3(G)\).
Notice that the equalities \[c(sx,y,z)=c(x,y,z),\ \ c(x,sy,z)=c(x,y,z, ),\ \ c(x,y,sz)=c(x,y,z),\] are equivalent to \(sx\sigma(y)z=x\sigma(y)z\), \(x\sigma(sy)z=x\sigma(y)z\) and \(x\sigma(y)sz=x\sigma(y)z\), respectively. In each case, we easily obtain \(s=e\).
Now suppose that either \(c(sx,sy,z)=c(x,y,z)\) or \(c(x,sy,sz)=c(x,y,z)\). Then either \(sx\sigma(sy)z=x\sigma(y)z\) or \(x\sigma(sy)sz=x\sigma(y)z\). In both cases, \(s\sigma(sy)=\sigma(y)\), so \(sy\sigma(sy)=y\sigma(y)\). Since the map \(x\mapsto x\sigma(x)\) is a bijection, we obtain \(s=e\).
Finally, consider the case \(c(sx,sy,sz)=c(x,y,z)\). Then \(sx\sigma(sy)sz=x\sigma(y)z\), so \(s^2\sigma(sy)=\sigma(y)\), and hence \((sy)^2\sigma(sy)=y^2\sigma(y)\). Since the map \(x\mapsto x^2\sigma(x)\) is a bijection, we obtain \(s=e\).
Therefore, the function \(c(x, y,z) =x\sigma(y)z\) defines a proper colouring for the graph \(\mathscr{G}_3(G)\). ◻
Applying Theorem 2.4 we obtain
Corollary 3.4. If \(G\) is a finite abelian group, such that the Sylow \(2\)-subgroup and the Sylow \(3\)-subgroup of \(G\) are either trivial or non-cyclic, then \(\chi(\mathscr{G}_3(G))=|G|\).
It is an open question whether \(\chi(\mathscr{G}_3(G)=|G|\) implies that the group \(G\) admits a double complete mapping. Interestingly, if \(G\) is an abelian group of odd order, then by expanding the connecting set \(\mathcal{S}\), we construct a graph \(\widehat{\mathscr{G}_3}(G)\) with a greater number of edges. For this graph, the condition \(\chi(\widehat{\mathscr{G}_3}(G))=|G|\) is equivalent to the existence of a double complete mapping on \(G\).
For a finite abelian group \(G\) let \(\widehat{\mathscr{G}_3}(G)\) be a Cayley graph over the Cartesian power \(G^3\) having the connection set \[\widehat{\mathcal{S}}=\mathcal{S} \cup \{ (x,e,x) \mid x \in G^{*} \} \cup \{ (x,x^2,x) \mid x \in G^{*} \},\] where \(\mathcal{S}= \mathcal{S}(3)\) is the connection set for \(\mathscr{G}_3(G)\). If the order of \(G\) is odd, then the graph \(\widehat{\mathscr{G}_3}(G)\) is \(k\)-regular, where \(k=8(|G|-1)\).
Proposition 3.5. If \(G\) is an abelian group of odd order, then \(\chi(\widehat{\mathscr{G}}_3(G))=|G|\) if and only if \(G\) admits a double complete mapping.
Proof. Suppose that \(G\) admits a double complete mapping \(\sigma\). We show that the function \(c(x,y,z)=x\sigma(y)z\) is a colouring mapping for the graph \(\widehat{\mathscr{G}_3}(G)\). In light of Proposition 3.3, it remains to prove that each of the equations: \[\begin{aligned} &c(sx,y,sz) =c(x,y,z), & & &c(sx,s^2y,sz) =c (x,y,z) , \end{aligned}\] implies \(s=e\). In the first case we have \(sx\sigma(y)sz=x\sigma(y)z\), so \(s^2=e\). Since the order \(|G|\) is odd, it follows \(s=e\). In the second case, \(sx\sigma(s^2y)sz=x\sigma(y)z\), which implies \(s^2\sigma(s^2y)=\sigma(y)\). Thus, \(s^2y\sigma(s^2y)=y\sigma(y)\). Since the map \(x\mapsto x\sigma(x)\) is a bijection, we obtain \(s^2=e\) and consequently \(s=e\). Therefore, the function \(c(x,y,z)\) defines a proper colouring of the graph \(\widehat{\mathscr{G}_3}(G)\).
Suppose that \(\chi(\widehat{\mathscr{G}}_3(G))=|G|\). Let \(c\colon G^3\to G\) be a coloring map. For any \(x\in G^*\) consider a clique \(V_x=\{(sx,s,sx)\mid\ s\in G\}\). Then there exists a unique element \(s=\sigma(x)\in G^*\) such that \[c(sx,s,sx)=c(e,e,e).\]
Since the vertices \((sx,s,sx)\) and \((sy,s,sy)\) are adjacent, we obtain that the map \(x\mapsto \sigma(x)\) is a bijection. Similarly, if \(\sigma(x)x=\sigma(y)y\), then the vertex \[(\sigma(x)x,x,\sigma(x)x)=(\sigma(y)y,x,\sigma(y)y),\] is adjacent to \((\sigma(y)y,y,\sigma(y)y)\). This is impossible, since both vertices have the same colour \(c(e,e,e)\). Thus, the mapping \(x\mapsto \sigma(x)x\) is a bijection.
Consider the map \(F\colon G^3\to G^3\) defined by \[F(x,y,z)=(x,xy^{-1}z,z).\]
The map \(F\) is a group automorphism of order two. Moreover, \[F(s,e,e)=(s,s,e),\ \ \ F(e,s,e)=(e,s^{-1},e),\ \ \ F(e,e,s)=(e,s,s),\] \[F(s,s,e)=(s,e,e), \ \ \ F(e,s,s)=(e,e,s),\ \ \ F(s,s,s)=(s,s,s),\] \[F(s,e,s)=(s,s^2,s) \ \ \ \text{ and }\ \ \ F(s,s^2,s)=(s,e,s).\]
Thus, \(F\) preserves the connecting set \(\widehat{\mathcal{S}}\), and consequently, \(F\) is a graph automorphism.
Notice that \[F(\sigma(x)x,\sigma(x),\sigma(x)x)=(\sigma(x)x,\sigma(x)x^2,\sigma(x)x).\]
Now it is clear that the mapping \(x\mapsto \sigma(x)x^2\) is a bijection. Indeed, if \(\sigma(x)x^2=\sigma(y)y^2\), then the vertices \[(\sigma(x)x,\sigma(x)x^2,\sigma(x)x) \text{ and } (\sigma(y)y,\sigma(x)x^2,\sigma(y)y)=(\sigma(y)y,\sigma(y)y^2,\sigma(y)y),\] are adjacent. Thus, the vertices \[F(\sigma(x)x,\sigma(x)x^2,\sigma(x)x) \text{ and } F(\sigma(y)y,\sigma(y)y^2,\sigma(y)y),\] are adjacent, which is impossible, since they have the same colour.
Consequently, the map \(x\mapsto \sigma(x)\) is double complete. ◻
The above considerations can be summarized in the following conclusion:
Theorem 3.6. If \(G\) is an abelian group of odd order and the Sylow \(3\)-subgroup of \(G\) is either trivial or non-cyclic, then \[\chi(\mathscr{G}_3(G))= \chi(\widehat{\mathscr{G}_3}(G))=|G|.\]
Calculations performed with the help of GAP [10] produced the results shown in the tables below. The question mark informs that we were not able to calculate the chromatic numbers. Classical computational algorithms do not provide answers in polynolmial time for counting \(\chi \left( \mathscr{G}_{3} \left(G\right) \right)\) and \(\chi \left(\widehat{\mathscr{G}_{3}} \left(G \right) \right)\); these graphs require specialized algorithms.
| \(G\) | \(\chi \left( \mathscr{G}_{2} \left(G\right) \right)\) | \(G\) | \(\chi \left( \mathscr{G}_{3} \left(G\right) \right)\) | \(\chi \left( \widehat{\mathscr{G}_{3}} \left(G \right) \right)\) |
|---|---|---|---|---|
| \(C_{2}\) | \(4\) | \(C_{2}\) | \(4\) | \(8\) |
| \(C_{4}\) | \(6\) | \(C_{3}\) | \(7\) | \(9\) |
| \(C_{6}\) | \(8\) | \(C_{4}\) | \(7\) | \(8\) |
| \(S_3\) | \(8\) | \(C_{6}\) | \(\geqslant 8\) | \(\geqslant 8\) |
| \(C_{8}\) | \(10\) | \(C_{9}\) | \(?\) | \(\geqslant 10\) |
The first table suggests the hypothesis \({\chi(\mathscr{G}_2(G))= |G|+2}\) for groups with cyclic nontrivial Sylow \(2\)-subgroups. This was confirmed for abelian groups by L. Goddyn, K. Halasz and E.S. Mahmoodian in [7]. It would be interesting to answer the question, what are the values of \(\chi \left( \mathscr{G}_{3} \left(G\right) \right)\) and \(\chi \left( \widehat{\mathscr{G}_{3}} \left(G \right) \right)\), when \(G\) is abelian with cyclic Sylow \(2\)-subgroup or cyclic Sylow \(3\)-subgroup.