1 Introduction

A one-factor of a graph G is a regular spanning subgraph of degree one. A one-factorization of a graph G is a set \({{\mathcal {F}}} = \{F_1, F_2, \ldots , F_n\}\) of edge-disjoint one-factors such that \(E(G) =\bigcup _{i=1}^n E(F_i)\). Two one-factorizations are orthogonal, if any pair of one-factors one from the first factorization and one from the second factorization have at most one edge in common. The existence of a pair of orthogonal one-factorizations of complete graph \(K_{n+1}\) is equivalent to the existence of a Room square of side n.

Let S be a set of \(n+1\) elements called symbols. A Room square of size n on S is an \(n\times n\) array, F, that satisfies the following properties:

  1. 1.

    Every cell of F is either empty or contains an unordered pair of symbols from S.

  2. 2.

    Each symbol of S occurs once in each row and column of F.

  3. 3.

    Every unordered pair of symbols occurs in precisely one cell of F.

Room squares were named after T. G. Room who published a paper in 1955. It is well known that a Room square of size n exists if and only if n is odd and \(n\ne 3\) or 5 [17].

One-factors and one-factorizations of complete graphs (and other graphs) arise naturally in the construction of round-robin tournaments and other competition schedules, and certainly they have been considered for a long time. One-factorizations have proved useful in the construction of designs such as Room squares and Steiner systems. For more details on one-factorizations of complete graphs, see the excellent surveys [1, 5, 9, 16].

A one-factorization \({{\mathcal {F}}} = \{F_1, F_2, \ldots , F_n\}\) of a graph G is said to be k-cycle free if the union of any two one-factors does not include a cycle of length k (denoted by \(C_k\)). The existence of a 4-cycle-free one-factorization of complete graph \(K_n\) for even \(n\ge 6\) has already been observed in [12], where they were used to give the existence of simple quadruple systems with index three. Generally, for each even n and each even \(k\ge 4\) with \(k\ne \frac{n}{2}\), the complete graph \(K_{n}\) has a k-cycle-free one-factorization [10].

Theorem 1

[12] A \(C_4\)-free one-factorization of complete graphs \(K_n\) exists if and only if n is even and \(n\ge 6\).

A pair of orthogonal one-factorizations \({\mathcal {F}}\) and \(\mathcal G\) of complete graph \(K_n\) is \(C_4\)-free if for any two factors \(F\in {\mathcal {F}}\) and \(G\in {\mathcal {G}}\) the union \(F\cup G\) does not include a cycle of length four. Such a concept was introduced by Blokhuis et al., who used it to improve the upper bound for two-round rainbow colorings of \(K_n\) [2].

A subgraph H of \(K_n\) is total multicolored (colored rainbow) if all its edges have different colors. A t-round \(\chi \)-coloring is defined as a sequence \(\psi _1, \ldots , \psi _t\) of t (not necessarily distinct) proper edge colorings of a complete graph, using at most \(\chi \) colors in each of the colorings. For positive integers \(k\le n\) and t, let \(\chi ^t (k, n)\) denote the minimum number \(\chi \) of colors for which there exists a t-round \(\chi \)-coloring of \(K_n\) such that each subgraph \(K_k\) of \(K_n\) is total multicolored in at least one round.

Blokhuis et al. [2] proved that

$$\begin{aligned} \frac{\sqrt{(n-1)n}}{\sqrt{2}} \le \chi ^2(4, n)\le 2n \end{aligned}$$

for \(n\ge 4\). When there is a pair of orthogonal \(C_4\)-free one-factorizations of a complete graph, this upper bound can be improved greatly.

Theorem 2

[2] If \(K_n\) has a pair of orthogonal \(C_4\)-free one-factorizations, then \(\chi ^2(4, n)\le n-1\).

In this paper, we shall focus on constructions of a pair of orthogonal \(C_4\)-free one-factorizations of complete graphs. Here we are also interested in pairs of orthogonal \(C_4\)-free one-factorizations of complete graphs with a strengthened property. A pair of orthogonal one-factorizations \({\mathcal {F}}\) and \(\mathcal G\) of complete graph \(K_n\) is totally \(C_4\)-free if for any two distinct factors \(F,G\in {\mathcal {F}}\cup {\mathcal {G}}\) the union \(F\cup G\) does not include a cycle of length four.

The rest of this paper is arranged as follows. In Sect. 2, we use starters to construct a pair of orthogonal totally \(C_4\)-free one-factorizations of complete graphs. In Sect. 3, a recursive construction is stated. In Sect. 4, we modify Horton’s Room squares [8] so that the two orthogonal one-factorizations are \(C_4\)-free. Some infinite classes of two orthogonal \(C_4\)-free one-factorizations of complete graphs are also given.

2 Starter Construction

The most useful technique for the direct construction of Room squares has been the technique of orthogonal starters. This technique was introduced in the mathematical literature in 1968 by Stanton and Mullin in [14].

Let G be an abelian group of odd order g. A starter in G is a set of unordered pairs \(S=\{\{s_i,t_i\}:1\le i\le (g-1)/2\}\) which satisfies the following two properties:

  1. (i)

    \(\{s_i:1\le i\le (g-1)/2\}\cup \{t_i:1\le i\le (g-1)/2\}=G{\setminus } \{0\}\);

  2. (ii)

    \(\{\pm (s_i-t_i):~1\le i\le (g-1)/2\}=G{\setminus } \{0\}\).

It is well known that \(F_a=\{\{\infty ,a\}\}\cup \{\{s_i+a,t_i+a\}:1\le i\le (g-1)/2\}\), \(a\in G\), forms a one-factorization of the complete graph on \(G\cup \{\infty \}\).

Let \(S=\{\{s_i,t_i\}:1\le i\le (g-1)/2\}\) and \(T=\{\{u_i,v_i\}:1\le i\le (g-1)/2\}\) be two starters in G. Without loss of generality, we may assume that \(s_i-t_i=u_i-v_i\) for all i. Then S and T are said to be orthogonal starters if \(u_i-s_i=u_j-s_j\) implies \(i=j\), and if \(u_i\ne s_i\) for all i.

Theorem 3

[14] If there are two orthogonal starters in an abelian group of odd order g, then there is a Room square of side g, i.e., a pair of orthogonal one-factorizations of complete graph \(K_{g+1}\).

If \(S=\{\{s_i,t_i\}:1\le i\le (g-1)/2\}\) is a starter, then \(-S=\{\{-s_i,-t_i\}:1\le i\le (g-1)/2\}\) is also a starter. In any abelian group G of odd order, the set of pairs \(P=\{\{x,-x\}:x\in G\}\) is a starter, called the patterned starter. A starter \(S=\{\{s_i,t_i\}:1\le i\le (g-1)/2\}\) is called strong if the sums \(s_i+t_i\) are distinct and nonzero.

Theorem 4

[7] If there is a strong starter S in an abelian group of odd order g, then S, \(-S\) and P are pairwise orthogonal.

Lemma 1

[6] For odd \(g\ge 5\), the one-factorization of \(K_{g+1}\) generated by patterned starter is \(C_4\)-free if and only if \( g \not \equiv 0 \pmod 3\).

Let q be a prime power with \(q=ef+1\) and GF(q) be the finite field of q elements. Given a primitive element \(\alpha \) of GF(q), define \(C_0^{(e,q)}=\{\alpha ^{je}:0\le j\le f-1\}\), the multiplicative group generated by \(\alpha ^e\), and

$$\begin{aligned} C_i^{(e,q)}=\alpha ^iC_0^{(e,q)} \end{aligned}$$

for \(1\le i\le e-1\). Then \(C_0^{(e,q)}, C_1^{(e,q)},\ldots , C_{e-1}^{(e,q)}\) partition \(GF(q)^*=GF(q){\setminus } \{0\}\). The \(C_i^{(e,q)}\) are known as cyclotomic classes of order e (with respect to GF(q)).

Theorem 5

[7] Let \(q\equiv 3\pmod 4\) be a prime power. For \(w\in C_1^{(2,q)}{\setminus } \{-1\}\), define \(T_w=\{\{x,wx\}:x\in C_0^{(2,q)}\}\). Then \(T_w\) is a strong starter. Further, \(T_w\) and \(T_u\) are orthogonal if \(w,u\in C_1^{(2,q)}{\setminus } \{-1\}\) and \(w\ne u\).

Lemma 2

Let \(q\equiv 3\pmod 4\) be a prime power and \(T_w\) as above. The one-factorization generated by the starter \(T_w\) is \(C_4\)-free if \(\{w, \frac{1+w^2}{2w}\} \subseteq C_1^{(2,q)}\) and \(w^3\ne -1\).

Proof

Let \(F_i=\{\{\infty ,i\}\}\cup \{\{x+i,wx+i\}:x\in C_0^{(2,q)}\}\) for \(i\in GF(q)\). Then \({{\mathcal {F}}}=\{F_i: i\in GF(q)\}\) is a one-factorization of the complete graph on \(GF(q)\cup \{\infty \}\). Assume that this one-factorization is not \(C_4\)-free. Since \(F_i=F_0+i\), without loss of generality, let \(F_0\cup F_i\) (\(i\ne 0\)) contain a cycle \(\{\{a,b\},\{a,c\},\{c,d\},\{b,d\}\}\) of length 4 where \(\{a,b\},\{c,d\}\in F_0\) and \(\{a,c\}, \{b,d\}\in F_i\). Then \(\{a-i,c-i\},\{b-i,d-i\}\in F_0\).

Case 1\(\infty \in \{a,b,c,d\}\).

Without loss of generality, let \(a=\infty \). Then \(b=0\) and \(c=i\). If \(i\in C_0^{(2,q)}\), then by the definition of \(T_w\) and \(-1\in C_1^{(2,q)}\) we have that \(d-i\in C_0^{(2,q)}\), \(d=wi\) and \(-i=w(d-i)\). It follows that \(w^2-w+1=0\), which contradicts the assumption that \(w^3\ne -1\). If \(i\in C_1^{(2,q)}\), then \(d-i\in C_1^{(2,q)}\), \(i=wd\) and \(d-i=-wi\). It follows that \(w^2-w+1=0\), which also contradicts the assumption that \(w^3\ne -1\).

Case 2\(\infty \not \in \{a,b,c,d\}\), i.e., \(\{a,b,c,d\}\subset GF(q)^*\).

Let \(\{a,b\}=\{x,wx\}\) where \(x\in C_0^{(2,q)}\). Since \(x^{-1}\cdot F_0=F_0\), we have that \(\{a/x,b/x\}, \{c/x,d/x\}\in F_0\) and \(\{a/x,c/x\}\), \(\{b/x,d/x\}\in F_{i/x}\), i.e., \(\{\{a/x,b/x\}, \{c/x,d/x\},\{a/x,c/x\},\{b/x,d/x\}\}\) is a cycle of length 4 in \(F_0\cup F_{i/x}\). For convenience, let \(a=1\) and \(b=w\). Since \(F_i=F_0+i\), \(\{1-i,c-i\}\), \(\{w-i,d-i\}\in F_0\). Clearly, \(1-i,c-i,w-i,d-i\in GF(q)^*\).

Subcase 1\(1-i,w-i,c\in C_0^{(2,q)}\).

By the definition of \(T_w\), we have that \(c-i=w(1-i)\), \(d-i=w(w-i)\) and \(d=wc\). Simple computation shows that \(w=1\), a contradiction.

Subcase 2\(1-i,w-i\in C_0^{(2,q)}\) and \(c\in C_1^{(2,q)}\).

By the definition of \(T_w\), we have \(c-i=w(1-i)\), \(d-i=w(w-i)\) and \(c=wd\). Simple computation shows \(i=\frac{w^2+w}{w-1}\). Since \(1-i, w-i\in C_0^{(2,q)}\), we have that \(1-i=\frac{-1-w^2}{w-1}, w-i=\frac{-2w}{w-1}\in C_0^{(2,q)}\). This is impossible because \(\frac{1+w^2}{2w}\in C_1^{(2,q)}\) by assumption.

Subcase 3\(1-i,c\in C_0^{(2,q)}\) and \(w-i\in C_1^{(2,q)}\).

By the definition of \(T_w\), we have \(c-i=w(1-i)\), \(w(d-i)=w-i\) and \(d=wc\). Simple computation shows that \(i=\frac{w^2+w}{w^2+1}\). Then \(c=i+w-wi=\frac{2w}{w^2+1}\in C_0^{(2,q)}\). This is impossible because \(\frac{1+w^2}{2w}\in C_1^{(2,q)}\) by assumption.

Subcase 4\(1-i\in C_0^{(2,q)}\) and \(w-i,c\in C_1^{(2,q)}\).

By the definition of \(T_w\), we have \(c-i=w(1-i)\), \(w(d-i)=w-i\) and \(c=wd\). Simple computation shows that \(w=1\), a contradiction.

Subcase 5\(1-i\in C_1^{(2,q)}\) and \(w-i,c\in C_0^{(2,q)}\).

By the definition of \(T_w\), we have \(1-i=w(c-i)\), \(d-i=w(w-i)\) and \(d=wc\). Simple computation shows \(i=\frac{w+1}{2}\). Then \(c=i+\frac{1-i}{w}=\frac{w^2+1}{2w}\in C_0^{(2,q)}\), which also contradicts the assumption that \(\frac{1+w^2}{2w}\in C_1^{(2,q)}\).

Subcase 6\(1-i,c\in C_1^{(2,q)}\) and \(w-i\in C_0^{(2,q)}\).

By the definition of \(T_w\), we have \(1-i=w(c-i)\), \(d-i=w(w-i)\) and \(c=wd\). Then \(i=1+w\) and \(d=i+w^2-wi=1=a\), a contradiction.

Subcase 7\(1-i, w-i\in C_1^{(2,q)}\) and \(c\in C_0^{(2,q)}\).

By the definition of \(T_w\), we have \(1-i=w(c-i)\), \(w-i=w(d-i)\) and \(d=wc\). Simple computation shows that \(w=1\), a contradiction.

Subcase 8\(1-i, w-i,c\in C_1^{(2,q)}\).

By the definition of \(T_w\), we have \(1-i=w(c-i)\), \(w-i=w(d-i)\) and \(c=wd\). Simple computation shows that \(i=\frac{1+w}{1-w}\). Then since \(1-i\in C_1^{(2,q)}\) and \(w-i\in C_1^{(2,q)}\), we have \(1-i=\frac{2w}{w-1}\in C_1^{(2,q)}\) and \(w-i=\frac{w^2+1}{w-1}\in C_1^{(2,q)}\), which also contradicts the assumption that \(\frac{1+w^2}{2w}\in C_1^{(2,q)}\). \(\square \)

Example 1

For \(q=19\), take \(w=13\). Then \(\frac{1+w^2}{2w}=8\in C_1^{(2,19)}\). Set

$$\begin{aligned} F_i=\left\{ \{\infty ,i\}\}\cup \{\{x+i,13x+i\}:x\in C_0^{(2,19)}\right\} \quad \ \mathrm{for}\; i\in GF(19). \end{aligned}$$

It is easy to check that one-factorization \({{\mathcal {F}}}=\{F_i: i\in GF(19)\}\) is \(C_4\)-free.

Lemma 3

Let \(q\equiv 3\pmod 4\) be a prime power and \(T_w\) be as above. The pair of orthogonal one-factorizations generated by the starter \(T_w\) and \(-T_w\) is \(C_4\)-free if \(w,\frac{1+w^2}{2w}\in C_1^{(2,q)}\), \(w\not \in \left\{ 2,\frac{1}{2}\right\} \) and \(w^3\ne -1\).

Proof

Let \(F_i=\{\{\infty ,i\}\}\cup \{\{x+i,wx+i\}:x\in C_0^{(2,q)}\}\) and \(G_i=\{\{\infty ,i\}\}\cup \{\{-x+i,-wx+i\}:x\in C_0^{(2,q)}\}\) for \(i\in GF(q)\). Then \({{\mathcal {F}}}=\{F_i: i\in GF(q)\}\) and \({{\mathcal {G}}}=\{G_i: i\in GF(q)\}\) are orthogonal one-factorizations of the complete graph on \(GF(q)\cup \{\infty \}\) by Theorems 3, 4 and 5. Assume that this pair of one-factorizations is not \(C_4\)-free. Since \(F_i=F_0+i\) and \(G_i=G_0+i\), without loss of generality, assume \(F_0\cup G_i\) (\(i\in GF(q)\)) contains a cycle \(\{\{a,b\},\{a,c\},\{c,d\},\{b,d\}\}\) of length 4 where \(\{a,b\},\{c,d\}\in F_0\) and \(\{a,c\},\{b,d\} \in G_i\). Then \(\{a-i,c-i\},\{b-i,d-i\} \in G_0\).

Case 1\(\infty \in \{a,b,c,d\}\).

Without loss of generality, let \(a=\infty \). Then \(b=0\) and \(c=i\). If \(i=0\), then \(c=b=0\), a contradiction. If \(i\in C_0^{(2,q)}\), then by the definition of \(T_w\), \(G_0\) and \(-1\in C_1^{(2,q)}\) we have \(d=wi\) and \(d-i=-wi\). It follows that \(w=1/2\), which contradicts the assumption that \(w\ne 1/2\). If \(i\in C_1^{(2,q)}\), then \(i=wd\) and \(w(d-i)=-i\). It follows that \(w=2\), which also contradicts the assumption that \(w\ne 2\).

Case 2\(\infty \not \in \{a,b,c,d\}\), i.e., \(\{a,b,c,d\}\subset GF(q)^*\).

Let \(\{a,b\}=\{x,wx\}\) where \(x\in C_0^{(2,q)}\). Since \(x^{-1}\cdot F_0=F_0\), we have \(\{a/x,b/x\}, \{c/x,d/x\}\in F_0\) and \(\{a/x,c/x\}\), \(\{b/x,d/x\}\in G_{i/x}\), i.e., \(\{\{a/x,b/x\}, \{c/x,d/x\},\{a/x,c/x\},\{b/x,d/x\}\}\) must be a cycle of length 4 in \(F_0\cup G_{i/x}\). For convenience, let \(a=1\) and \(b=w\). Since \(G_i=G_0+i\), \(\{1-i,c-i\}\), \(\{w-i,d-i\}\in G_0\), i.e., \(\{i-1,i-c\}\), \(\{i-w,i-d\}\in F_0\).

Since \(q\equiv 3\pmod 4\), we have \(-1\in C_1^{(2,q)}\). According to which cyclotomic classes \(i-1,i-w,c\) belong to, there are eight possible subcases. No matter which case occurs, it must be equivalent to some subcase of Lemma 2. For example, the case when \(i-1,i-w,c\in C_0^{(2,q)}\) is equivalent to Subcase 7 of Lemma 2. The same arguments arrive at a contradiction to the assumptions. \(\square \)

In the theory of cyclotomy, the number of solutions of

$$\begin{aligned} x+1=y,\quad x\in C_i^{(e,q)},\quad y\in C_j^{(e,q)} \end{aligned}$$

is called cyclotomic number of order e respect to GF(q) and denoted \((i,j)_e\). The following basic properties of the cyclotomic numbers were established by Dickson [4].

Theorem 6

[4] Let q be a prime power with \(q=ef+1\). Then

$$\begin{aligned} \begin{array}{l} (1)(i,j)_e=(e-i,j-i),\\ (2)(i,j)=\left\{ \begin{array}{ll} (j,i)_e, &{} \quad \mathrm{if}\; 2|f,\\ (j+\frac{e}{2},i+\frac{e}{2}), &{} \quad \mathrm{if}\; 2 \not | f;\\ \end{array} \right. \\ (3) \sum _{j=0}^{e-1}(i,j)_e=\left\{ \begin{array}{ll} f-1, &{} \quad \mathrm{if}\; 2|f\ \;\mathrm{and}\ i=0,\\ f-1, &{} \quad \mathrm{if}\; 2 \not | f\ \;\mathrm{and}\ i=\frac{e}{2},\\ f, &{} \quad \mathrm{otherwise}; \end{array} \right. \\ (4) \sum _{i=0}^{e-1}(i,j)_e=\left\{ \begin{array}{ll} f-1, &{} \quad \mathrm{if}\; j=0,\\ f, &{} \quad \mathrm{if}\; j\ne 0. \end{array} \right. \end{array} \end{aligned}$$

Some cyclotomic numbers have been determined. The reader is referred to [15].

Theorem 7

For any prime power \(q\equiv 3\pmod 4\) with \(q\ge 11\), there is a pair of orthogonal totally \(C_4\)-free one-factorizations of \(K_{q+1}\).

Proof

Let \(M=\left\{ w: w\in C_1^{(2,q)}, w \not \in \left\{ 2, \frac{1}{2} \right\} , w^3\ne -1\ \mathrm{and}\ \frac{w^2+1}{2w}\in C_1^{(2,q)}\right\} \). By Lemmas 2 and 3, we need only show that M is not the empty set.

Let the characteristic of the finite field GF(q) be p. Then \(q=p^n\). Since \(q\equiv 3\pmod 4\), it holds that \(p\equiv 3\pmod 4\) and n is odd. Let \(\alpha \) be a primitive element of GF(q) and \(m=\frac{p^n-1}{p-1}\). Then m is odd and \(\{\alpha ^{mi}:0\le i\le p-2\}=GF(p)^*\). Let \(2=\alpha ^{mj}\). Clearly, if 2 also belongs to \(C_0^{(2,p)}\), then 2 belongs to \(C_0^{(2,q)}\). Conversely, if 2 belongs to \(C_0^{(2,q)}\), then j is even because m is odd. So, \(2=(\alpha ^{mj/2})^2\in C_0^{(2,p)}\). These show that 2 is a quadratic residue modulo p if and only if 2 is a quadratic residue in GF(q). Also, by Theorem 6 it is easy to see that \((0,0)_2=(1,0)_2=(1,1)_2=\frac{f-1}{2}\) and \((0,1)_2=\frac{f+1}{2}\).

For \(q\equiv 7,23\pmod {24}\) with \(q\ge 11\), it is easy to see that char\((GF(q))=p\equiv 7\pmod 8\). Since 2 is a quadratic residue in \({\mathbb {Z}}_p\) by elementary number theory, 2 is a quadratic residue in GF(q). Since \((0,0)_2=\frac{q-3}{4}\ge 4\), there are at least four elements \(y\in C_0^{(2,q)}\) such that \(1+y\in C_0^{(2,q)}\). Since \(-1\in C_1^{(2,q)}\), there is an \(x\in C_1^{(2,q)}\) such that \(x^2=y\). On the other hand, there are at most three elements z in \(C_1^{(2,q)}\) such that \(z^3=-1\). So, there is at least one element \(w\in C_1^{(2,q)}\) such that \(w^3\ne -1\) and \(1+w^2\in C_0^{(2,q)}\). Such an element w belongs to M, thus \(M\ne \emptyset \).

For \(q\equiv 11,19\pmod {24}\) with \(q\ge 23\), it is easy to see that char\((GF(q))=p\equiv 3\pmod 8\). Since 2 is a quadratic non-residue in \({\mathbb {Z}}_p\) by elementary number theory, 2 is also a quadratic non-residue in GF(q). Since \((0,1)_2=\frac{q+1}{4}\ge 6\), there are at least six elements \(y\in C_0^{(2,q)}\) such that \(1+y\in C_1^{(2,q)}\). Since \(-1\in C_1^{(2,q)}\), there is an \(x\in C_1^{(2,q)}\) such that \(x^2=y\). On the other hand, there are at most three elements z in \(C_1^{(2,q)}\) such that \(z^3=-1\). So, there is at least one element \(w\in C_1^{(2,q)}\) such that \(w^3\ne -1\), \(w\ne 2,\frac{1}{2}\) and \(1+w^2\in C_1^{(2,q)}\). Such an element w belongs to M, i.e., \(M\ne \emptyset \). For \(q=11\), take \(w=8\) and for \(q=19\), take \(w=13\). It is routine check that \(w\in M\). \(\square \)

Example 2

For \(q=19\), take \(w=13\). Then \(\frac{1+w^2}{2w}=8\in C_1^{(2,19)}\). Set

$$\begin{aligned} \begin{array}{llllllllllll} F_i=\left\{ \{\infty ,i\}\}\cup \{\{x+i,13x+i\}:x\in C_0^{(2,19)}\right\} \quad \ \mathrm{and} \\ G_i=\left\{ \{\infty ,i\}\}\cup \{\{18x+i,6x+i\}:x\in C_0^{(2,19)}\right\} \quad \mathrm{for}\; i\in GF(19). \end{array} \end{aligned}$$

It is easy to check that the pair of one-factorizations \(\mathcal{F}=\{F_i: i\in GF(19)\}\) and \({{\mathcal {G}}}=\{G_i: i\in GF(19)\}\) is totally \(C_4\)-free.

Let \(q=2^kt+1\) be an odd prime power, where \(t\ge 3\) is odd. For \(w\in C_{2^{k-1}}^{(2^k,q)}\), let \(A=\cup _{i=0}^{2^{k-1}-1}C_i^{(2^k,q)}\) and \(S_w=\{\{x,wx\}:x\in A\}\). Then each \(S_w\) is a starter, where \(S_{-1}\) is the patterned starter. It is easy to see that each \(S_w\) is a strong starter for \(w\in C_{2^{k-1}}^{(2^k,q)}{\setminus } \{-1\}\).

Lemma 4

Let \(q=2^kt+1\ge 9\) be an odd prime power, where t is odd and \(k \ge 1\). The pair of orthogonal one-factorizations of \(K_{q+1}\) generated by the starters \(S_w\) and \(S_{-1}\) is \(C_4\)-free, where \(w\in C_{2^{k-1}}^{(2^k,q)}{\setminus } \left\{ -1, 2, \frac{1}{2}\right\} \).

Proof

Denote \(F_i=\{\{\infty ,i\}\}\cup \{\{x+i,-x+i\}:x\in A\}\) and \(G_i=\{\{\infty ,i\}\}\cup \{\{x+i,wx+i\}:x\in A\}\) for \(i\in GF(q)\). Since \(S_w\) is a strong starter for each \(w\in C_{2^{k-1}}^{(2^k,q)}{\setminus } \{-1\}\), by Theorems 3 and 4 we have \({{\mathcal {F}}}=\{F_i: i\in GF(q)\}\) and \({{\mathcal {G}}}=\{G_i: i\in GF(q)\}\) are orthogonal one-factorizations of the complete graph on \(GF(q)\cup \{\infty \}\). Assume that this pair of one-factorizations is not \(C_4\)-free. Since \(F_i=F_0+i\) and \(G_i=G_0+i\), \(F_i\cup G_j\) contains a \(C_4\) if and only if \(F_{i-j}\cup G_0\) contains a \(C_4\). Let \(F_i\cup G_0\) (\(i\in GF(q)\)) contains a cycle \(\{\{a,b\},\{a,c\},\{c,d\},\{b,d\}\}\) of length 4 where \(\{a,b\},\{c,d\}\in G_0\) and \(\{a,c\},\{b,d\}\in F_i\). Then \(\{a-i,c-i\},\{b-i,d-i\}\in F_0\).

Case 1\(\infty \in \{a,b,c,d\}\).

Without loss of generality, let \(a=\infty \). Then \(b=0\) and \(c=i\). By the definition of \(F_i\) we have \(b+d=d=2i=2c\). Hence \(\frac{d}{c}=2\). On the other hand, it holds that \(\frac{d}{c}=w\) or \(\frac{1}{w}\) by the definition of \(G_0\). So, we arrive at a contradiction because \(w\notin \left\{ 2,\frac{1}{2}\right\} \) by assumption.

Case 2\(\infty \not \in \{a,b,c,d\}\), i.e., \(\{a,b,c,d\}\subset GF(q)^*\).

Let \(\{a,b\}=\{x,wx\}\) and \(\{c,d\}=\{y,wy\}\) where \(x,y\in A\) and \(x\ne y\). By the definition of \(F_i\), it holds that \(a+c=2i=b+d\). So, \(x+y=wx+wy\) or \(x+wy=y+wx\). It follows that \(w=1\), or \(x+y=0\), or \(x=y\). Since \(x,y\in A=\cup _{i=0}^{2^{k-1}-1}C_i^{(2^k,q)}\) and \(t\ge 3\) is odd, we have \(-1\in C_{2^{k-1}}^{(2^k,q)}\) and \(x+y\ne 0\). Also, \(w\ne 1\) and \(x\ne y\) by definition. Thus, we arrive at a contradiction. \(\square \)

Corollary 1

Let \(q=p^s=2^kt+1\ge 9\) be an odd prime power where \(p\ge 5\) is a prime and \(t\ge 3\) is odd. Then there is a pair of orthogonal \(C_4\)-free one-factorizations of \(K_{q+1}\).

Proof

By Lemma 4, we need only to show that there is an element \(w\in C_{2^{k-1}}^{(2^k,q)}{\setminus } \left\{ -1, 2,\frac{1}{2}\right\} \). If \(t>3\), clearly such an element exists. If \(t=3\), it holds that \(2\not \in C_{2^{k-1}}^{(2^k,q)}\). Assume that it does not hold. Then we have \(2=\alpha ^{2^ks+2^{k-1}}\), where \(\alpha \) is a primitive element of GF(q). It follows that \(8=2^t=(\alpha ^{2^ks+2^{k-1}})^t=\alpha ^{2^{k-1}t}=-1\). It follows that q is divisible by 3, a contradiction. Also, \(\frac{1}{2}\not \in C_{2^{k-1}}^{(2^k,q)}\). So, there is an element \(w\in C_{2^{k-1}}^{(2^k,q)}{\setminus } \left\{ -1, 2,\frac{1}{2}\right\} \). \(\square \)

Lemma 5

Let \(q=2^kt+1\ge 9\) be an odd prime power where \(t\ge 3\) is odd. If the one-factorization of \(K_{q+1}\) generated by \(S_w\), \(w\in C_{2^{k-1}}^{(2^k,q)}\), is not \(C_4\)-free, then \(w^2-w+1=0\), or there is an element \(x\in A=\cup _{i=0}^{2^{k-1}-1}C_i^{(2^k,q)}\) such that both \(\frac{2w}{1-w}x\) and \(\frac{1+w^2}{1-w}x\) are contained in A, or both \(\frac{w^2+1}{2w}x\) and \(\frac{w-1}{2}x\) are contained in A.

Proof

Denote \(G_i=\{\{\infty ,i\}\}\cup \{\{x+i,wx+i\}:x\in A\}\) for \(i\in GF(q)\). Then \({{\mathcal {G}}}=\{G_i: i\in GF(q)\}\) is a one-factorization of the complete graph on \(GF(q)\cup \{\infty \}\). Assume that this one-factorization is not \(C_4\)-free. Since \(G_i=G_0+i\), \(G_i\cup G_j\) contains a \(C_4\) if and only if \(G_{i-j}\cup G_0\) contains a \(C_4\). Suppose \(G_i\cup G_0\) (\(i\in GF(q)^*\)) contains a cycle \(\{\{a,b\},\{a,c\},\{c,d\},\{b,d\}\}\) of length 4 where \(\{a,b\},\{c,d\}\in G_0\) and \(\{a,c\},\{b,d\}\in G_i\).

If \(\infty \in \{a,b,c,d\}\), without loss of generality, let \(a=\infty \). Then \(b=0\) and \(c=i\). By the definition of \(G_0\), if \(c\in A\), then \(d=wc\) and \(-c\not \in A\). It follows that \(d-c\in A\) and \(-c=w(d-c)\). Thus, \(w^2-w+1=0\), a contradiction. If \(c\not \in A\), then \(c=wd\) and \(-c\in A\). It follows that \(d-c\not \in A\) and \(d-c=-wc\). Thus, \(w^2-w+1=0\), a contradiction.

Suppose that \(\infty \not \in \{a,b,c,d\}\) and let \(\{a,b\}=\{y,wy\}\) and \(\{c,d\}=\{z,wz\}\) where \(y,z\in A\) and \(y\ne z\). We consider the following two cases.

Case 1\(\{y,z\}\), \(\{wy,wz\}\in G_i\), i.e., \(\{y-i,z-i\},\{wy-i,wz-i\}\in G_0\).

If \(z-i, wz-i\in A\), then \(y-i=w(z-i)\) and \(wy-i=w(wz-i)\). It follows that \((w-1)y=w(w-1)z\). Since \(w\ne 1\), we have \(y=wz\). This is impossible because \(y,z\in A\) and \(w\in C_{2^{k-1}}^{(2^k,q)}\). Similar arguments show that it is impossible for \(y-i, wy-i\in A\).

If \(z-i, wy-i\in A\), then \(y-i=w(z-i)\) and \(wz-i=w(wy-i)\). After subtracting the second equation from the first, we obtain \(z=\frac{1+w^2}{2w}y\). It follows that \(i=\frac{w+1}{2}y\). Since \(z-i, wy-i\in A\), we deduce \(z-i=\frac{1-w}{2w}y\in A\) and \(wy-i=\frac{w-1}{2}y\in A\). Clearly, \(\frac{-1}{w}\in C_0^{(2^k,q)}\). Therefore, \(\frac{1-w}{2w}y\in A\) if and only if \(\frac{w-1}{2}y\in A\). So, if there is a cycle of length 4, there is an element \(x \in A\) such that \(\frac{1+w^2}{2w}x \in A\) and \(\frac{w-1}{2}x\in A\). When \(y-i, wz-i\in A\), similar arguments also show that there is such an element \(x\in A\).

Case 2\(\{y,wz\}\), \(\{z,wy\}\in G_i\), i.e., \(\{y-i,wz-i\},\{z-i,wy-i\}\in G_0\).

If \(z-i, wz-i\in A\), then \(y-i=w(wz-i)\) and \(wy-i=w(z-i)\). It follows that \(y=-wz\). By substitution, we get \(i=\frac{w^2+w}{w-1}z\). Since \(z-i, wz-i\in A\), both \(\frac{2w}{1-w}z\) and \(\frac{1+w^2}{1-w}z\) belong to A. When \(y-i,wy-i\in A\), same arguments also show that there is an element \(x\in A\) such that both \(\frac{2w}{1-w}x\) and \(\frac{1+w^2}{1-w}x\) belong to A.

If \(z-i, y-i\in A\), then \(wy-i=w(z-i)\) and \(wz-i=w(y-i)\). It follows that \(w(y-z)=w(z-y)\). Then \(w=0\), a contradiction.

If \(wy-i, wz-i\in A\), then \(y-i=w(wz-i)\) and \(z-i=w(wy-i)\). It follows that \(y-z=w^2(z-y)\). Then \(w^2=-1\), contradicting \(w^2\in C_0^{(2^k,q)}\). \(\square \)

Lemma 6

Let q be a prime power with \(q\not \equiv 0 \pmod 3\). If \(q\equiv 5\pmod 8\) or \(q\equiv 9\pmod {16}\), then there is a pair of orthogonal totally \(C_4\)-free one-factorizations of \(K_{q+1}\) for \(q\ge 13\).

Proof

Let the characteristic of the finite field GF(q) be p and \(q=p^n\). We shall show that there is an element \(w\in C_{2^{k-1}}^{(2^k,q)}{\setminus } \left\{ -1,2,\frac{1}{2}\right\} \) such that \(\frac{w-1}{2}\in C_{2^{k-1}}^{(2^k,q)}\) and \(w^2-w+1\ne 0\). Then by Lemmas 4 and 5, the pair of orthogonal one-factorizations of \(K_{q+1}\) generated by the starters \(S_w\) and \(S_{-1}\) is totally \(C_4\)-free.

If \(q\equiv 5\pmod 8\), then \(p\equiv 5\pmod 8\) and n is odd. Similar to the proof Theorem 7, 2 is a quadratic non-residue in GF(q). Write \(q=s^2+4t^2\). By [15, Lemma 19 in Part 1], we have \((3,2)_4=\frac{q+1+2s-8t}{16}\) and \((1,2)_4=\frac{q+1+2s+8t}{16}\). Clearly, \((s\pm 4t)^2=s^2+16t^2\pm 8st\le 5(s^2+4t^2)=5q\). When \(q\ge 113\), \((3,2)_4=\frac{q+1+2s-8t}{16}\ge \frac{q+1-2\sqrt{5q}}{16}\ge 4\). Also, \((1,2)_4\ge 4\). If \(2\in C_{1}^{(4,q)}\), there are at least four elements \(w\in C_{2}^{(4,q)}\) such that \(w-1\in C_{3}^{(4,q)}\), which yields \(\frac{w-1}{2}\in C_{2}^{(4,q)}\). So, there is at least one element \(w\in C_{2}^{(4,q)}\) such that \( w\not \in \left\{ -1,2,\frac{1}{2}\right\} \), \(w^2-w+1\ne 0\) and \(\frac{w-1}{2}\in C_{2}^{(4,q)}\). If \(2\in C_{3}^{(4,q)}\), there are at least four elements \(w\in C_{2}^{(4,q)}\) such that \(w-1\in C_{1}^{(4,q)}\), which yields \(\frac{w-1}{2}\in C_{2}^{(4,q)}\). So, there is at least one element \(w\in C_{2}^{(4,q)}\) such that \( w\not \in \left\{ -1,2,\frac{1}{2}\right\} \), \(w^2-w+1\ne 0\) and \(\frac{w-1}{2}\in C_{2}^{(4,q)}\).

For \(q\equiv 9\pmod {16}\), write \(q=s^2+4t^2\) where \(s\equiv 1\pmod 4\). By [15, Lemma 30 in Part 1], if \(2\in C_0^{(4,q)}\), then \((0,4)_8=\frac{q+1-18s}{64}\) and \((4,4)_8=\frac{q-15-2s}{64}\); if \(2\notin C_0^{(4,q)}\), then \((2,4)_8=\frac{q+1-2s-16t}{64}\) and \((6,4)_8=\frac{q+1-2s+16t}{64}\). Clearly, \((-s\pm 8t)^2=s^2+64t^2\pm 16st\le 17(s^2+4t^2)=17q\). When \(q\ge 666\) and \(2\in C_2^{(4,q)}\), we have \((2,4)_8=\frac{q+1-2s-16t}{64}\ge \frac{q+1-2\sqrt{17q}}{64}\ge 4\). Similarly, \((6,4)_8\ge 4\) when \(q\ge 666\) and \(2\in C_2^{(4,q)}\). Also, when \(q\ge 936\) and \(2\in C_0^{(4,q)}\), we have \((0,4)_8=\frac{q+1-18s}{64}\ge \frac{q+1-18\sqrt{q}}{64}\ge 6\). Similarly, \((2,4)_8\ge 6\), \((4,4)_8\ge 6\) and \((6,4)_8\ge 6\) when \(q\ge 936\) and \(2\in C_0^{(4,q)}\).

For \(q\equiv 9\pmod {16}\), we have \(p\equiv 3,5\pmod 8\) and \(n\equiv 2\pmod 4\), or \(p\equiv 9\pmod {16}\) and n is odd. Similar to the proof Theorem 7, 2 is a quadratic residue in GF(q). Moreover, \(2\in C_2^{(4,q)}\) if \(p\equiv 5\pmod {8}\), and \(2\in C_4^{(8,q)}\) if \(p\equiv 3\pmod {8}\).

For \(q=p^n\equiv 9\pmod {16}\) with \(p\equiv 5\pmod 8\) and \(q\ge 666\), if \(2\in C_2^{(8,q)}\), there are at least four elements \(w\in C_4^{(8,q)}\) such that \(w-1\in C_6^{(8,q)}\). This is because \((6,4)_8\ge 4\). So, there is at least one element \(w\in C_4^{(8,q)}\) such that \( w\not \in \left\{ -1,2,\frac{1}{2}\right\} \), \(w^2-w+1\ne 0\) and \(\frac{w-1}{2}\in C_4^{(8,q)}\). If \(2\in C_6^{(8,q)}\), since \((2,4)_8\ge 4\), there is at least one element \(w\in C_4^{(8,q)}\) such that \( w\not \in \left\{ -1,2,\frac{1}{2}\right\} \), \(w^2-w+1\ne 0\) and \(\frac{w-1}{2}\in C_4^{(8,q)}\).

For \(q=p^n\equiv 9\pmod {16}\) with \(p\equiv 3\pmod 8\) and \(q\ge 936\). Since \((0,4)_8\ge 6\), \((2,4)_8\ge 6\), \((4,4)_8\ge 6\) and \((6,4)_8\ge 6\), there is at least one element \(w\in C_4^{(8,q)}\) such that \( w\not \in \left\{ -1,2,\frac{1}{2}\right\} \), \(w^2-w+1\ne 0\) and \(\frac{w-1}{2}\in C_4^{(8,q)}\).

For \(q=p^n\equiv 9\pmod {16}\) with \(p\equiv 9\pmod {16}\) and \(q\ge 936\), if \(2\in C_2^{(8,q)}\), there are at least six elements \(w\in C_4^{(8,q)}\) such that \(w-1\in C_6^{(8,q)}\). This is because \((6,4)_8\ge 6\). So, there is at least one element \(w\in C_4^{(8,q)}\) such that \( w\not \in \left\{ -1,2,\frac{1}{2}\right\} \), \(w^2-w+1\ne 0\) and \(\frac{w-1}{2}\in C_4^{(8,q)}\). If \(2\in C_4^{(8,q)}\), \(2\in C_6^{(8,q)}\) or \(2\in C_0^{(8,q)}\), a similar argument shows that there is at least one element \(w\in C_4^{(8,q)}\) such that \( w\not \in \left\{ -1,2,\frac{1}{2}\right\} \), \(w^2-w+1\ne 0\) and \(\frac{w-1}{2}\in C_4^{(8,q)}\).

We next consider small prime powers q. For any prime \(q\in \{29,53,61,101, 109,137,233,281,313,409,\)\(457,521,569,601,617,761,809,857\}\), we list the required element w which satisfies the conditions in Lemma 5.

q

w

q

w

q

w

29

9

53

6

61

36

233

170

281

126

313

108

569

444

601

599

617

171

q

w

q

w

q

w

101

64

109

4

137

18

409

144

457

254

521

404

761

18

809

373

857

102

For \(q\in \{37,41,73,89\}\), a strong starter S is constructed in \({\mathbb {Z}}_{q}\) with multiplier group \(\{\xi ^i:1\le i\le N\}\). The shortened list of pairs is as follows:

$$\begin{aligned} \begin{array}{llllllllllll} q=37,\ \xi =7,\ N=9: &{} \{1,2\}, &{}\{3,17\}. \\ q=41,\ \xi =10,\ N=5: &{} \{1,2\}, &{}\{3,15\}, &{}\{4,39\}, &{}\{6,11\}.\\ q=73,\ \xi =2,\ N=9: &{} \{1,3\}, &{}\{5,15\}, &{}\{9,33\}, &{}\{13,35\}.\\ q=89,\ \xi =2,\ N=11: &{} \{1,3\}, &{}\{5,18\}, &{}\{11,31\}, &{}\{19,43\}.\\ \end{array} \end{aligned}$$

It is readily checked that the two orthogonal one-factorizations of \(K_{q+1}\) generated by S and \(-S\) are totally \(C_4\)-free.

For \(q\in \{25,121,169,361\}\), let the finite field GF(q) be generated by the primitive polynomial f(x) and let \(\theta \) be a primitive element of GF(q). Denote the field elements \(0,\theta ^1,\theta ^2,\ldots ,\theta ^{q-1}\) by \(0, 1, 2,\ldots , q-1\). A strong starter S is constructed over GF(q) with multiplier group \(\{\xi ^i:1\le i\le N\}\). The shortened list of pairs is as follows.

q

f(x)

\(\xi \)

N

Shortened list of pairs

25

\(x^2+3x+3\)

\(\theta ^8\)

3

{1,2}, {3,7}, {4,13}, {6,8}.

121

\(x^2+10x+8\)

\(\theta ^8\)

15

{1,2}, {3,4}, {5,64}, {6,39}.

169

\(x^2+9x+11\)

\(\theta ^8\)

21

{1,2}, {3,4}, {5,63}, {6,136}.

361

\(x^2+15x+15\)

\(\theta ^{40}\)

9

{1,2}, {3,4}, {5,6}, {7,8}, {9,10}, {11,12},

    

{13,14},{15,16}, {17,18}, {19,20},{21,35},

    

{22,193}, {23,105}, {24,271}, {26,38},{27,109},

    

{28,199},{30,276},{32,280}, {34,37}.

It is easy to check that the two orthogonal one-factorizations of \(K_{q+1}\) by S and \(-S\) are totally \(C_4\)-free.

For \(q=13\), we construct two orthogonal starters in \({\mathbb {Z}}_q\) as follows:

$$\begin{aligned} \begin{array}{llllllllllll} S=\{\{ 1, 2\}, &{} \{ 3, 6\}, &{} \{ 4,11\}, &{} \{ 5, 9\}, &{} \{ 7,12\}, &{} \{ 8,10\}\},\\ T=\{\{ 1, 6\}, &{} \{ 2, 9\}, &{} \{ 3, 5\}, &{} \{ 4, 7\}, &{} \{ 8,12\}, &{} \{10,11\}\}.\\ \end{array} \end{aligned}$$

It is easy to check that the two orthogonal one-factorizations of \(K_{q+1}\) generated by S and T are totally \(C_4\)-free. \(\square \)

3 Product Construction

A Latin square of order n is an \(n\times n\) matrix with entries from an n-set V, where every row and every column is a permutation of V. A one-factorization of complete bipartite graph \(K_{n,n}\) is equivalent to a Latin square of order n. A \(C_4\)-free one-factorization of \(K_{n,n}\) is equivalent a Latin square without a subsquare of order 2. In 1991, Heinrich [3] proved that Latin squares without a subsquare of order 2 exist for all orders \(n \not \in \{2,4\}\).

In order to state our product construction for a pair of orthogonal one-factorizations of \(K_n\), we need a pair of orthogonal one-factorizations of the complete bipartite graph such that the union of any two factors does not include a cycle of length 4, which we succinctly call totally \(C_4\)-free.

Let \({{\mathcal {F}}}=\{F_1,F_2,\ldots ,F_n\}\) and \(\mathcal{G}=\{G_1,G_2,\ldots ,G_n\}\) be a pair of orthogonal one-factorizations of \(K_{n,n}\) with bipartition X and Y where \(|X|=|Y|=n\) and \(X\cap Y=\emptyset \). By definition, \(|F_i\cap G_j|=1\) for \(i,j \in \{1,2,\ldots ,n\}\). Define an \(n\times n\) array such that its (i, j)-th entry is \(F_i\cap G_j\). By definition, the union of the i-th row is \(F_i\), the union of the j-th column is \(G_j\). Define two \(n\times n\) arrays \(L_1\) and \(L_2\) with rows indexed by X and columns indexed by Y. The (x, y)-th entry of \(L_1\) is i if \(\{x,y\}\) in \(F_i\) and (x, y)-th entry of \(L_2\) is j if \(\{x,y\}\) in \(G_j\). It is well known that such two arrays are Latin squares and orthogonal. Two Latin squares \(A=(a_{i,j})\) and \(B=(b_{i,j})\) of order n from n-sets V and S, respectively, are said to be orthogonal if \(\{(a_{i,j},b_{i,j}):1\le i\le n, 1\le j\le n\}=V\times S\). Conversely, a pair of orthogonal one-factorizations of \(K_{n,n}\) can be obtained from two orthogonal Latin squares.

Suppose that the two orthogonal one-factorizations of \(K_{n,n}\) are totally \(C_4\)-free. Since there is no \(C_4\) in any union of \(F_i\cup F_j\), there is no subsquare of order 2 in \(L_1\) (Otherwise, there exist \(x_1\ne x_2\) and \(y_1\ne y_2\) such that \(L_1(x_1,y_1)=L_1(x_2,y_2)\) and \(L_1(x_1,y_2)=L_1(x_2,y_1)\), then pairs \(\{x_1,y_1\}\) and \(\{x_2,y_2\}\) are in \(F_{L_1(x_1,y_1)}\), and pairs \(\{x_1,y_2\}\) and \(\{x_2,y_1\}\) are in \(F_{L_1(x_1,y_2)}\). These pairs form a \(C_4\) in \(F_{L_1(x_1,y_2)}\cup F_{L_1(x_1,y_2)}\), which contradicts that no \(F_i\cup F_j\) include a \(C_4\)). Likewise, \(L_2\) contains no subsquare of order 2. Further, there does not exist \(x_1\ne x_2\) and \(y_1\ne y_2\) such that \(L_1(x_1,y_1)=L_1(x_2,y_2)\) and \(L_2(x_1,y_2)=L_2(x_2,y_1)\) (Otherwise, pairs \(\{x_1,y_1\}\) and \(\{x_2,y_2\}\) are in \(F_{L_1(x_1,y_1)}\), and pairs \(\{x_1,y_2\}\) and \(\{x_2,y_1\}\) are in \(G_{L_2(x_1,y_2)}\). These pairs form a \(C_4\) in \(F_{L_1(x_1,y_2)}\cup G_{L_2(x_1,y_2)}\), which contradicts that no \(F_i\cup G_j\) include a \(C_4\)). Conversely, we obtain two orthogonal totally \(C_4\)-free one-factorizations of \(K_{n,n}\) from two orthogonal Latin squares \(L_1=(L_1(x,y))\) and \(L_2=(L_2(x,y))\) of order n each without a subsquare of order 2 and there do not exist \(x_1\ne x_2,y_1\ne y_2\) such that \(L_1(x_1,y_1)=L_1(x_2,y_2)\) and \(L_2(x_1,y_2)=L_2(x_2,y_1)\). This fact is stated below.

Lemma 7

There are two orthogonal totally \(C_4\)-free one-factorizations of the complete bipartite graph \(K_{n,n}\) if and only if there are two orthogonal Latin squares \(L_1=(L_1(x,y))\) and \(L_2=(L_2(x,y))\) of order n each without a subsquare of order 2 and there do not exist \(x_1\ne x_2,y_1\ne y_2\) such that \(L_1(x_1,y_1)=L_1(x_2,y_2)\) and \(L_2(x_1,y_2)=L_2(x_2,y_1)\).

Lemma 8

For any integer \(n\equiv 1,5\pmod 6\) where \(n\ge 5\), there is a pair of orthogonal totally \(C_4\)-free one-factorizations of \(K_{n,n}\).

Proof

Define two one-factorizations of \(K_{n,n}\) on \({\mathbb {Z}}_n\times \{1,2\}\) with bipartition \({\mathbb {Z}}_n\times \{i\}\), \(i\in \{1,2\}\) as follows:

$$\begin{aligned} \begin{array}{l} {{\mathcal {F}}}=\{F_a=\{\{(x,1),(a-x,2)\}:x\in {\mathbb {Z}}_n\}:a\in {\mathbb {Z}}_n\},\\ {{\mathcal {G}}}=\{G_a=\{\{(x,1),(a-2x,2)\}:x\in {\mathbb {Z}}_n\}:a\in {\mathbb {Z}}_n\}.\\ \end{array} \end{aligned}$$

It is easy to check that \({{\mathcal {F}}}\) and \(\mathcal{G}\) are orthogonal.

We prove that \({\mathcal {F}}\) is \(C_4\)-free. Assume that \(F_a\cup F_b\) (\(a\ne b\)) includes a \(C_4\). Suppose that two edges \(\{(x,1),(a-x,2)\}\) and \(\{(y,1),(a-y,2)\}\)\((x\ne y)\) of \(F_a\) are contained in a \(C_4\). Then the other two edges \(\{(x,1),(a-y,2)\}\) and \(\{(y,1),(a-x,2)\}\) are contained in \(F_b\). It follows that \(x+a-y=y+a-x=b\). So, \(2x=2y\). Since n is odd, we have \(x=y\), which is a contradiction. Similarly, we can show that \({\mathcal {G}}\) is \(C_4\)-free.

We show that for any \(F_a\in {{\mathcal {F}}}\) and \(G_b\in {{\mathcal {G}}}\), \(F_a\cup G_b\) does not include a \(C_4\). If it is not true, then we can assume that two edges \(\{(x,1),(a-x,2)\}\) and \(\{(y,1),(a-y,2)\}\)\((x\ne y)\) of \(F_a\) are contained in a \(C_4\). Then the other two edges \(\{(x,1),(a-y,2)\}\) and \(\{(y,1),(a-x,2)\}\) are contained in \(G_b\). It follows that \(2x+a-y=2y+a-x=b\). So, \(3x=3y\). Since \(n\equiv 1,5\pmod 6\), we have \(x=y\), which is a contradiction. This completes the proof. \(\square \)

Lemma 9

For any \(q=3^k\) with \(k\ge 2\), there is a pair of orthogonal totally \(C_4\)-free one-factorizations of \(K_{q,q}\).

Proof

Let \(\alpha \) be a primitive element of the finite field GF(q). Define two one-factorizations of \(K_{q,q}\) on \(GF(q)\times \{1,2\}\) with bipartition \(GF(q)\times \{i\}\), \(i\in \{1,2\}\) as follows:

$$\begin{aligned} \begin{array}{l} {{\mathcal {H}}}=\{H_a=\{\{(x,1),(\alpha (a-x),2)\}:x\in GF(q)\}:a\in GF(q)\},\\ {{\mathcal {G}}}=\{G_a=\{\{(x,1),((a-x)(1+\alpha ),2)\}:x\in GF(q)\}:a\in GF(q)\}.\\ \end{array} \end{aligned}$$

It is easy to check that \({{\mathcal {F}}}\) and \(\mathcal{G}\) are orthogonal.

We prove that \({\mathcal {H}}\) is \(C_4\)-free. If it does not hold, assume that \(H_a\cup H_b\) (\(a\ne b\)) includes a \(C_4\). Suppose that two edges \(\{(x,1),(\alpha (a-x),2)\}\) and \(\{(y,1),(\alpha (a-y),2)\}\)\((x\ne y)\) of \(H_a\) are contained in a \(C_4\). Then the other two edges \(\{(x,1),(\alpha (a-y),2)\}\) and \(\{(y,1),(\alpha (a-x),2)\}\) are contained in \(H_b\). It follows that \(\alpha (a-y)=\alpha (b-x)\) and \(\alpha (a-x)=\alpha (b-y)\). So, \(\alpha (x-y)=\alpha (y-x)\). Then \(x=y\), a contradiction. Similarly, we can show that \({\mathcal {G}}\) is \(C_4\)-free.

We show that for any \(H_a\in {{\mathcal {H}}}\) and \(G_b\in {{\mathcal {G}}}\), \(H_a\cup G_b\) does not include a \(C_4\). If it is not true, then we can assume that two edges \(\{(x,1),(\alpha (a-x),2)\}\) and \(\{(y,1),(\alpha (a-y),2)\}\)\((x\ne y)\) of \(H_a\) are contained in a \(C_4\). Then the other two edges \(\{(x,1),(\alpha (a-y),2)\}\) and \(\{(y,1),(\alpha (a-x),2)\}\) are contained in \(G_b\). It follows that \(\alpha (a-y)=(1+\alpha )(b-x)\) and \(\alpha (a-x)=(1+\alpha )(b-y)\). So, \(\alpha (x-y)=(1+\alpha )(y-x)\). Then \(\alpha =-\frac{1}{2}=1\), which is a contradiction since \(\alpha \) is a primitive element. This completes the proof. \(\square \)

Lemma 10

If there is a pair of orthogonal totally \(C_4\)-free one-factorizations of \(K_{m,m}\) and a pair of orthogonal totally \(C_4\)-free one-factorizations of \(K_{n,n}\), then there is a pair of orthogonal totally \(C_4\)-free one-factorizations of \(K_{mn,mn}\)

Proof

Let \({{\mathcal {F}}}=\{F_1,F_2,\ldots ,F_m\}\) and \(\mathcal{G}=\{G_1,G_2,\ldots ,G_m\}\) be two orthogonal totally \(C_4\)-free one-factorizations of \(K_{m,m}\) on \(V\times \{1,2\}\) with bipartition \(V\times \{1\}\) and \(V\times \{2\}\). Let \(\mathcal{H}=\{H_1,H_2,\ldots ,H_m\}\) and let \({{\mathcal {Q}}}=\{Q_1,Q_2,\ldots ,Q_m\}\) be two orthogonal totally \(C_4\)-free one-factorizations of \(K_{n,n}\) on \(S\times \{1,2\}\) with bipartition \(S\times \{1\}\) and \(S\times \{2\}\). For \(1\le i\le m\) and \(1\le j\le n\), define

$$\begin{aligned}&A(F_i,H_j)=\{\{(x_1,y_1,1),(x_2,y_2,2)\}:\{(x_1,1),(x_2,2)\}\in F_i,\{(y_1,1),(y_2,2)\}\in H_j\},\\&B(G_i,Q_j)=\{\{(x_1,y_1,1),(x_2,y_2,2)\}:\{(x_1,1),(x_2,2)\}\in G_i,\{(y_1,1),(y_2,2)\}\in Q_j\}. \end{aligned}$$

It is routine to check that \(\{A(F_i,H_j):1\le i\le m,1\le j\le n\}\) and \(\{B(G_i,Q_j):1\le i\le m,1\le j\le n\}\) form a pair of orthogonal totally \(C_4\)-free one-factorizations of \(K_{mn,mn}\). \(\square \)

Applying Lemma 10 with the known pairs of orthogonal totally \(C_4\)-free one-factorizations of \(K_{n,n}\) in Lemmas 8 and 9, we obtain the following theorem.

Theorem 8

For any odd positive integer n with \(gcd(n,9)\ne 3\), there is a pair of orthogonal totally \(C_4\)-free one-factorizations of \(K_{n,n}\).

With the aid of a pair of orthogonal totally \(C_4\)-free one-factorizations of \(K_{m,m}\), we are now in a position to state a recursive construction of pairs of orthogonal totally \(C_4\)-free one-factorizations of \(K_{n}\). Such a construction is obtained by modifying the construction for Room squares.

Theorem 9

Suppose that there is a pair of orthogonal totally \(C_4\)-free one-factorizations of \(K_{n,n}\), two orthogonal totally \(C_4\)-free one-factorizations of \(K_{n+1}\) and \(K_{m+1}\), then there are two orthogonal totally \(C_4\)-free one-factorizations of \(K_{nm+1}\).

Proof

We prove it in term of Room squares. By the equivalence between a Room square and a pair of orthogonal one-factorizations of complete graph, let M and N be the standardized Room squares of orders m and n, respectively, which correspond to pairs of orthogonal totally \(C_4\)-free one-factorizations of complete graph of orders m and n. The symbol sets are \(\{\infty ,1,2,\ldots ,m\}\) and \(\{\infty ,1,2,\ldots ,n\}\) respectively. Let A and B be two orthogonal Latin squares of order n on \(\{1,2,\ldots ,n\}\), which corresponds to a pair of orthogonal totally \(C_4\)-free one-factorizations of \(K_{n,n}\), i.e., A and B have no subsquare of order 2 and there do not exist four elements \(x,y,z,w\in \{1,2,\ldots ,n\}\), \(x\ne z\), \(y\ne w\) such that \(A(x,y)=A(z,w)\) and \(B(x,w)=B(z,y)\). We shall construct a Room square of order mn on \(S=\{\infty ,1_1,1_2,\ldots ,1_m,2_1,\ldots ,2_m,\ldots ,n_1,n_2,\ldots ,n_m\}\).

For \(1\le i\le m\), we write \(A_i\) to mean A with every entry given a subscript i: If A has (1,1) entry x, then \(A_i\) has (1,1) entry \(x_i\). \(B_i\) is defined similarly. For \(1\le i,j\le m\), \(Q_{ij}\) is an \(n\times n\) array of unordered pairs whose (k, l) entry consists of the (k, l) entries of \(A_i\) and \(B_j\). We also subscript the arrays N, the pair \(\{x,y\}\) from N would be replaced by \(\{x_i,y_i\}\), where \(x_i=x\) when \(x=\infty \), the empty cells of N would correspond to empty cells of \(N_i\).

We first convert M into an \(mn\times mn\) array U by replacing each of its cells by an \(n\times n\) array. An empty cell is replaced by an empty \(n\times n\) array; the entry \(\{\infty ,i\}\) is replaced by \(N_i\); and the entry \(\{i,j\}\), \(i\ne j\), is replaced by \(Q_{ij}\).

By the Multiplication Theorem [13], U is a Room square of order mn. It is left to check that the two orthogonal one-factorizations of \(K_{mn+1}\) on S from rows and columns are totally \(C_4\)-free.

Assume that there is a cycle of length 4 in the union of any two distinct one-factors from rows and columns of U. Let \(\{a_s,b_t\}, \{c_i,d_j\} ,\{a_s,c_i\},\{b_t,d_j\}\) be such a cycle where \(\{a_s,b_t\}, \{c_i,d_j\} \) are from one-factor and \(\{a_s,c_i\},\{b_t,d_j\}\) are from another one-factor. From the above construction of U, it is easy to see that \(\{s,t\},\{i,j\}\) must be from a one-factor of M and \(\{s,i\},\{t,j\}\) must be also from a one-factor of M (they may be from the same one-factor). If \(s=t\), then \(i=s=j\). These four unordered pairs are from the same Room square \(N_s\), i.e., this cycle is contained in the union of two one-factors from rows and columns of \(N_s\). This gives a contradiction because \(N_s\) is totally \(C_4\)-free. A similar contradiction occurs for \(i=j\). Let \(s\ne t\) and \(i\ne j\). If \(\{s,t\}=\{i,j\}\), then these four unordered pairs are from the same array \(Q_{ij}\). This is impossible because there is no \(C_4\) in any union of two rows, or two columns, or one row and one column of \(Q_{ij}\). If \(\{s,t\}\ne \{i,j\}\), by projection we obtain that \(\{s,t\},\{i,j\}\) are in the same row or column of Room square M and \(\{s,i\}\) and \(\{t,j\}\) are in the same row or column of Room square M. We also arrive a contradiction since M is totally \(C_4\)-free. This completes the proof. \(\square \)

Theorem 10

Let n be an positive integer of the form \(n=3^{a_1}5^{a_2}7^{a_3}p_1^{\alpha _1}\cdots p_t^{\alpha _t}\) where each \(p_i\ge 11\) is a prime, \(p_i\not \equiv 1\pmod {16}\), \(a_1,a_2,a_3,\alpha _1,\ldots ,\alpha _t\) are non-negative integers and \(a_1\notin \{1,2\}\), \(a_2,a_3\ne 1\). Then there is a pair of orthogonal totally \(C_4\)-free one-factorizations of \(K_{n+1}\).

Proof

By Theorem 7, there exists a pair of orthogonal totally \(C_4\)-free one-factorizations of \(K_{3^{2k+1}+1}\) with \(k>0\). We construct a pair of orthogonal totally \(C_4\)-free one-factorizations of \(K_{3^{4}+1}\) as follows. For \(n=81\), let the finite field GF(81) be generated by the primitive polynomial \(f(x)=x^4+5x+5\) and let \(\theta \) be a primitive element of GF(81). Denote the field elements \(0,\theta ^1,\theta ^2,\ldots ,\theta ^{80}\) by \(0, 1, 2,\ldots , 80\). A strong starter S is constructed in GF(81) with multiplier group \(\{\theta ^{16},\theta ^{32},\theta ^{48},\theta ^{64},\theta ^{80}\}\). The shortened list of pairs is below.

$$\begin{aligned} \begin{array}{llllllllllll} \{1,2\}, &{}\{3,4\}, &{}\{5,6\}, &{}\{7,8\}, &{}\{9,58\}, &{}\{11,60\}, &{}\{13,62\}, &{}\{15,64\}.\\ \end{array} \end{aligned}$$

It is easy to check that the two orthogonal one-factorizations of \(K_{82}\) over \(GF(81)\cup \{\infty \}\) generated by S and \(-S\) are totally \(C_4\)-free. So, by applying Theorems 7 and 9 with the known two orthogonal totally \(C_4\)-free one-factorizations of \(K_{3^i,3^i}\) in Theorem 8, we obtain a pair of orthogonal totally \(C_4\)-free one-factorizations of \(K_{3^{a_1}+1}\) for each \(a_1\ge 3\).

By Lemma 6, there exists a pair of orthogonal totally \(C_4\)-free one-factorizations of \(K_{n+1}\) for \(n\in \{25,125\}\). Applying Theorem 9 with the known two orthogonal totally \(C_4\)-free one-factorizations of \(K_{5^i,5^i}\) in Theorem 8, we obtain a pair of orthogonal totally \(C_4\)-free one-factorizations of \(K_{5^{a_2}+1}\) for each \(a_2\ne 1\).

By Theorem 7, there exists a pair of orthogonal totally \(C_4\)-free one-factorizations of \(K_{7^{2k+1}+1}\) with \(k>0\). For \(n=49\), let the finite field GF(49) be generated by the primitive polynomial \(f(x)=x^2+5x+5\) and let \(\theta \) be a primitive element of GF(49). Denote the field elements \(0,\theta ^1,\theta ^2,\ldots ,\theta ^{48}\) by \(0, 1, 2,\ldots , 48\). A strong starter S is constructed in GF(49) with multiplier group \(\{\theta ^{16},\theta ^{32},\theta ^{48}\}\). The shortened list of pairs is below.

$$\begin{aligned} \{1, 2\}, \{3, 4\}, \{5, 8\}, \{6, 7\}, \{9, 26\}, \{11, 44\}, \{13, 32\}, \{14, 47\}. \end{aligned}$$

It is easy to check that the two orthogonal one-factorizations of \(K_{50}\) over \(GF(49)\cup \{\infty \}\) generated by S and \(-S\) are totally \(C_4\)-free. Applying Theorem 9 with the known two orthogonal totally \(C_4\)-free one-factorizations of \(K_{7^i,7^i}\) in Theorem 8, we obtain a pair of orthogonal totally \(C_4\)-free one-factorizations of \(K_{7^{a_3}+1}\) for each \(a_3\ne 1\).

By Theorem 7 and Lemma 6, there exists a pair of orthogonal totally \(C_4\)-free one-factorizations of \(K_{n+1}\) for \(n\in \{p_1,p_2,\ldots ,p_t\}\). Further, applying Theorem 9 with the known two orthogonal totally \(C_4\)-free one-factorizations of \(K_{m,m}\) in Theorem 8 yields the result. \(\square \)

4 Two Orthogonal \(C_4\)-free One-factorizations

In this section, we only consider two orthogonal \(C_4\)-free one-factorizations of \(K_n\), i.e, any union of two one-factors from two distinct one-factorizations does not include a \(C_4\).

We modify Horton’s Room squares [8] so that the corresponding two orthogonal one-factorizations are \(C_4\)-free.

Theorem 11

Let G be an abelian group of odd order n where \( n\not \equiv 0 \pmod 3\) and \(n\ge 7\). If there is a strong starter \(X=\{\{x_i,y_i\}:1\le i\le \frac{n-1}{2}\}\) in G such that \(\frac{x_i}{y_i}\not \in \left\{ \frac{1}{2},2\right\} \) for \(1\le i\le \frac{n-1}{2}\), \(x_i+x_j\ne y_i+y_j\) and \(x_i+y_j\ne x_j+y_i\) for any \(1\le i<j\le \frac{n-1}{2}\), then there is a pair of orthogonal \(C_4\)-free one-factorizations of \(K_{5n+1}\).

Proof

We first construct two orthogonal starters on \({\mathbb {Z}}_5\times G\). For \((i,j)\in {\mathbb {Z}}_5\times G\), let

$$\begin{aligned} F(i,j)=\{\{\infty ,(i,j)\}\}\cup \{\{(s+i,t+j),(i-s,j-t)\}:(s,t)\in {\mathbb {Z}}_5\times G{\setminus } \{(0,0)\}\}. \end{aligned}$$

Then all F(i, j) form a one-factorization of \(K_{5n+1}\) on \(\{\infty \}\cup ({\mathbb {Z}}_5\times G)\) and \(F(0,0){\setminus } \{\{\infty ,(0,0)\}\}\) is the patterned starter on \({\mathbb {Z}}_5\times G\).

For the starter X, we shall find two distinct non-zero elements a and b in G such that \(a+b\ne 0\) and \(5a\ne 3b\) and there is no pair \(\{x, y\}\) in X whose sum is a or b. This can be done as follows. For \(a,b\ne 0\), if \(5a=3b\) and \(5b=3a\), then \(25a=9a\). Since n is odd, it follows from \(16a=0\) that \(a=0\), a contradiction. Hence, it holds that \(5a\ne 3b\), or \(5b\ne 3a\) for any \(a\ne 0\) and \(b\ne 0\). Without loss of generality, let \(5a\ne 3b\). There are only \((n- 1)/2\) elements in the set of sums of X, while there are \(n- 1\) non-zero elements in G. Since \(n\ge 7\), we have \(n-1-\frac{n-1}{2}\ge 3\). Thus, we conclude that there exist two distinct non-zero elements a, b in G satisfying our conditions. Let \(h = \frac{b- a}{4}\) and \(g =\frac{a}{2}\). Now partition the nonzero elements of G into two sets P and N such that x is in P if and only if \(-x\) is in N. We add the restrictions: If \(-6x=a\), then let x belong to P; since \(5a\ne 3b\), we have \(-6(-h)\ne a\) and we can let h belong to P; since \(a+b\ne 0\), we have \(-6\times \frac{h}{3}\ne a\) and we can let \(-\frac{h}{3}\in P\). Now we consider the sets of pairs:

$$\begin{aligned}&A = \{\{(0, x), (0, y)\}: \{x, y\}\in X\}, \\&B = \{\{(1, x + g), (2, 2x + g)\}: x\in P, x\ne h\},\\&C = \{\{(4, x + g), (3, 2x + g)\}: x\in P, x\ne h\},\\&D = \{\{(1, x + g), (3, 2x + g)\}: x\in N\}, \\&E = \{\{(4, x + g), (2, 2x + g)\}: x\in N\}, \\&F = \{\{(1, h + g), (2, g)\}, \{(4, h + g), (3, g)\},\\&\qquad \quad \{(1, g), (4, g)\}, \{(2, 2h + g), (3, 2h + g)\}\}. \end{aligned}$$

From the proof of the main theorem in [8], the union of these 6 sets forms a strong starter M in \({\mathbb {Z}}_5\times G\). By Theorem 4, this strong starter M and the patterned starter \(F(0,0){\setminus } \{\{\infty ,(0,0)\}\}\) are orthogonal. Let \(M(0,0)=M\cup \{\{\infty ,(0,0)\}\}\) and \(M(i,j)=M(0,0)+(i,j)\) for \((i,j)\in {\mathbb {Z}}_5\times G\). By Theorem 3, the two one-factorizations \(\{M(i,j):(i,j)\in {\mathbb {Z}}_5\times G\}\) and \(\{F(i,j): (i,j) \in {\mathbb {Z}}_5\times G\}\) are orthogonal. It is left to show that any union of M(i, j) and \(F(i_1,j_1)\) does not include a cycle of length four. Since \(M(i,j)=M(0,0)+(i,j)\) and \(F(i,j)=F(0,0)+(i,j)\), we need only to show that any union of M(0, 0) and F(i, j) does not include a cycle of length four.

Assume that the union of M(0, 0) and F(i, j) contains a \(C_4\). Let \(\{(a_1,b_1), (a_2,b_2)\},\{(a_3,b_3),(a_4,b_4)\}\in M(0,0)\) and \(\{(a_1,b_1),(a_4,b_4)\},\{(a_3,b_3),(a_2,b_2)\} \in F(i,j)\), where \((a_1,b_1),(a_2,b_2),(a_3,b_3),(a_4,b_4)\) are distinct. According to the occurrence of \(\infty \) in this \(C_4\), we divided the proof into two cases.

Case 1\(\infty \in \{(a_1,b_1),(a_2,b_2),(a_3,b_3),(a_4,b_4)\}\).

Without loss of generality, let \((a_1,b_1)=\infty \). Then \((a_2,b_2)=(0,0)\) and \((a_4,b_4)=(i,j)\). By the definition of F(i, j), \((0,0)+(a_3,b_3)=(2i,2j)\) since \(\{(a_3,b_3),(a_2,b_2)\}\in F(i,j)\). It follows that \(\{(i,j),(2i,2j)\}\in M\). If \(i=0\), then \(\{j,2j\}\in X\) from the definition of M. This contradicts the assumption on the strong starter X that \(\frac{y}{z}\not \in \left\{ \frac{1}{2},2\right\} \) for any \(\{y,z\}\in X\). If \(i=1\), then \(\{(1,j),(2,2j)\}\in B\) or \(\{(1,j),(2,2j)\}=\{(1, h + g), (2, g)\}\in F\). When the former case occurs, by the definition of B there is some \(x\in P\) such that \(x+g=j\) and \(2j=2x+g\). Then \(g=0\), this is a contradiction because \(g=\frac{a}{2}\ne 0\). When \(\{(1,j),(2,2j)\}=\{(1, h + g), (2, g)\}\), we have \(2h+g=0\). This is also a contradiction because \(2h+g=2\times \frac{b-a}{4}+\frac{a}{2}=\frac{b}{2}\ne 0\). Similar arguments also show that it is impossible for \(i=4\). If \(i=2\), then \(\{(2,j),(4,2j)\}\in E\). By the definition of E, there is some \(x\in N\) such that \(2x+g=j\) and \(2j=x+g\). Then \(3x+g=0\), i.e., \(-6x=a\). By the restriction of P and N, there is no element \(x\in N\) such that \(-6x=a\). We then get a contradiction. Similar arguments also show that it is impossible for \(i=3\).

Case 2\(\infty \not \in \{(a_1,b_1),(a_2,b_2),(a_3,b_3),(a_4,b_4)\}\).

By the definition of F(i, j), it holds that \((2i,2j)=(a_1,b_1)+(a_4,b_4)=(a_2,b_2)+(a_3,b_3).\)

If \(\{(a_1,b_1),(a_2,b_2)\},\{(a_3,b_3),(a_4,b_4)\}\in A\), then \(\{b_1,b_2\},\{b_3,b_4\}\in X\) and \(b_1+b_4=b_2+b_3\). It is a contradiction because \(b_1+b_4\ne b_2+b_3\) by assumption. Clearly, this is impossible when \(\{(a_1,b_1),(a_2,b_2)\}\in A\) and \(\{(a_3,b_3),(a_4,b_4)\}\not \in A\).

If \(\{(a_1,b_1),(a_2,b_2)\},\{(a_3,b_3),(a_4,b_4)\}\in B\), then there are two distinct elements x, y from \(P{\setminus } \{h\}\) such that \(x+g+2y+g=2x+g+y+g\). It follows that \(x=y\), a contradiction. If \(\{(a_1,b_1),(a_2,b_2)\}\in B\) and \(\{(a_3,b_3),(a_4,b_4)\}\not \in B\), then \(\{(a_3,b_3),(a_4,b_4)\}\) must be from C or F. When \(\{(a_3,b_3),(a_4,b_4)\}\in C\), there are two elements \(x,y\in P{\setminus } \{h\}\) such that \(\{(a_1,b_1),(a_2,b_2)\}=\{(1,x+g),(2,2x+g)\}\) and \(\{(a_3,b_3),(a_4,b_4)\}=\{(4,y+g),(3,2y+g)\}\). It follows that \(x+g+y+g=2x+g+2y+g\). Then \(y=-x\), which contradicts the restriction on P and N that \(x\in P\) if and only if \(-x\in N\). Consider \(\{(a_3,b_3),(a_4,b_4)\}\in F\). When \(\{(a_3,b_3),(a_4,b_4)\}=\{(1, h + g), (2, g)\}\), there is an element \(x\in P{\setminus } \{h\}\) such that \(x+g+g=2x+g+h+g\). Then \(x=-h\). This is a contradiction since \(-h\in N\). When \(\{(a_3,b_3),(a_4,b_4)\}=\{(4, h + g), (3, g)\}\), there is an element \(x\in P{\setminus } \{h\}\) such that \(x+g+h+g=2x+g+g\). Then \(x=h\), a contradiction. When \(\{(a_3,b_3),(a_4,b_4)\}=\{(2, 2h + g), (3, 2h+g)\}\), then there is an element \(x\in P{\setminus } \{h\}\) such that \(x+g+2h+g=2x+g+2h+g\). Then \(x=0\), a contradiction.

If \(\{(a_1,b_1),(a_2,b_2)\},\{(a_3,b_3),(a_4,b_4)\}\in C\), then there are two distinct elements \(x,y \in P{\setminus } \{h\}\) such that \(x+g+2y+g=2x+g+y+g\). It follows that \(x=y\), a contradiction. For \(\{(a_1,b_1),(a_2,b_2)\}\in C\) and \(\{(a_3,b_3),(a_4,b_4)\}\not \in C\), we need only consider \(\{(a_3,b_3),(a_4,b_4)\}\) from F. When \(\{(a_3,b_3),(a_4,b_4)\}=\{(1, h + g), (2, g)\}\), there is an element \(x\in P{\setminus } \{h\}\) such that \(x+g+h+g=2x+g+g\). Then \(x=h\), a contradiction. When \(\{(a_3,b_3),(a_4,b_4)\}=\{(4, h + g), (3, g)\}\), there is an element \(x\in P{\setminus } \{h\}\) such that \(x+g+g=2x+g+h+g\). Then \(x=-h\). This is a contradiction since \(-h\in N\). When \(\{(a_3,b_3),(a_4,b_4)\}=\{(2, 2h + g), (3, 2h+g)\}\), there is an element \(x\in P{\setminus } \{h\}\) such that \(x+g+2h+g=2x+g+2h+g\). Then \(x=0\), a contradiction.

If \(\{(a_1,b_1),(a_2,b_2)\},\{(a_3,b_3),(a_4,b_4)\}\in D\), then there are two distinct elements x, y from N such that \(x+g+2y+g=2x+g+y+g\). It follows that \(x=y\), a contradiction. If \(\{(a_1,b_1),(a_2,b_2)\}\in D\) and \(\{(a_3,b_3),(a_4,b_4)\}\not \in D\), then \(\{(a_3,b_3),(a_4,b_4)\}\) must be from E or \(\{(a_3,b_3),(a_4,b_4)\}=\{(1,g),(4,g)\}\in F\). If \(\{(a_3,b_3),(a_4,b_4)\}\in E\), then there are two elements \(x,y\in N\) such that \(\{(a_1,b_1),(a_2,b_2)\}=\{(1,y+g),(3,2y+g)\}\) and \(\{(a_3,b_3),(a_4,b_4)\}=\{(4,x+g),(2,2x+g)\}\). It follows that \(x+g+y+g=2x+g+2y+g\). Then \(y=-x\), which contradicts the restriction on P and N that \(x\in P\) if and only if \(-x\in N\). If \(\{(a_3,b_3),(a_4,b_4)\}=\{(1, g), (4, g)\}\), then there is an element \(x\in N\) such that \(x+g+g=2x+g+g\). Then \(x=0\), a contradiction. Similar arguments show that this is impossible for \(|E|\ge 1\). If two edges are from F, then \(h=0\), a contradiction. So, there does not exist a \(C_4\) in the union of M(i, j) and \(F(i_1,j_1)\). This completes the proof. \(\square \)

Example 3

For \(n=11\), let

$$\begin{aligned} X=\{\{1,7\}, \{4,6\}, \{5,2\}, \{9,8\}, \{3, 10\}\}. \end{aligned}$$

It is easy to check that \(\frac{x_i}{y_i}\not \in \left\{ \frac{1}{2},2\right\} \) for \(\{x_i,y_i\}\in X\), \(x_i+x_j\ne y_i+y_j\) and \(x_i+y_j\ne x_j+y_i\) for any \(\{x_i,y_i\} \in X\) and \(i\not =j\). Let \(a=3\) and \(b=1\). Then we have \(a+b\ne 0\), \(5a\ne 3b\) and \(5b\ne 3a\). Set \(h = \frac{b-a}{4}=5\), \(g =\frac{a}{2}=7\), \(P=\{1,2,3,4,5\}\) and \(N=\{6,7,8,9,10\}\). Now we consider the sets of pairs:

$$\begin{aligned} A= & {} \{\{(0,1),(0,7)\}, \{(0,4),(0,6)\}, \{(0,5),(0,2)\}, \{(0,9),(0,8)\}, \{(0,3), (0,10)\}\},\\ B= & {} \{\{(1,8),(2,9)\}, \{(1,9),(2,0)\}, \{(1,10),(2,2)\}, \{(1,0),(2,4)\}\},\\ C= & {} \{\{(4,8),(3,9)\}, \{(4,9),(3,0)\}, \{(4,10),(3,2)\}, \{(4,0),(3,4)\}\},\\ D= & {} \{\{(1,2),(3,8)\}, \{(1,3),(3,10)\}, \{(1,4),(3,1)\}, \{(1,5),(3,3)\}, \{(1,6),(3,5)\}\},\\ E= & {} \{\{(4,2),(2,8)\}, \{(4,3),(2,10)\}, \{(4,4),(2,1)\}, \{(4,5),(2,3)\}, \{(4,6),(2,5)\}\},\\ F= & {} \{\{(1,1),(2,7)\}, \{(4,1),(3,7)\}, \{(1,7),(4,7)\}, \{(2,6),(3,6)\}\}, \\ M(0,0)= & {} \{\{\infty ,(0,0)\}\} \cup A \cup B \cup C \cup D \cup E \cup F, \\ M(i,j)= & {} M(0,0)+(i,j)\ \mathrm{for}\ (i,j)\in {\mathbb {Z}}_5\times G,\ \mathrm{and} \\ F(i,j)= & {} \{\{\infty ,(i,j)\}\}\cup \{\{(s,t),(2i-s,2j-t)\}:(s,t)\in {\mathbb {Z}}_5\times G{\setminus } \{(i,j)\}\}\ \nonumber \\&\mathrm{for}\ (i,j)\in {\mathbb {Z}}_5\times G. \end{aligned}$$

It is readily checked that any union of M(i, j) and \(F(i_1,j_1)\) does not include a cycle of length four.

Similar to the proof of Theorem 9, we have the following theorem.

Theorem 12

Suppose there is a pair of orthogonal \(C_4\)-free one-factorizations of \(K_{n,n}\), two orthogonal \(C_4\)-free one-factorizations of \(K_{n+1}\) and \(K_{m+1}\), then there is a pair of orthogonal \(C_4\)-free one-factorizations of \(K_{nm+1}\).

Theorem 13

Let \(n=3^a5^bp_1^{\alpha _1}p_2^{\alpha _2}\cdots p_k^{\alpha _k}\) where \(p_i>5\) are distinct primes, \(\alpha _1,\ldots ,\alpha _k\) are non-negative integers and \(a\not \in \{1,2\}\). If each \(p_i\) is a non-Fermat prime and \(5^bp_1^{\alpha _1}p_2^{\alpha _2}\cdots p_k^{\alpha _k}\ge 7\), then there is a pair of orthogonal \(C_4\)-free one-factorizations of \(K_{n+1}\).

Proof

For \(n\in \{7,35\}\), it is easy to check that the two one-factorizations generated by the following starter A and the patterned starter in \({\mathbb {Z}}_n\) are orthogonal and \(C_4\)-free.

$$\begin{aligned} n= & {} 7: \{\{1,3\},\{2,6\},\{4,5\}\}\\ n= & {} 35: \{\{1,3\},\{2,5\},\{4,9\},\{6,7\},\{8,12\},\{10,19\},\{11,24\},\{13,25\}, \{14,29\},\\&\{15,31\}, \{16,33\},\{17,28\},\{18,26\},\{20,34\},\{21,27\},\{22,32\},\{23,30\}\}\\ \end{aligned}$$

By applying Theorem 12 repeatedly with the known pair of orthogonal \(C_4\)-free one-factorizations of \(K_{7,7}\) in Theorem 8, there is a pair of orthogonal \(C_4\)-free one-factorizations of \(K_{7^k+1}\) for any positive integer k. Similarly, by Theorems 12 and 8, there is a pair of orthogonal \(C_4\)-free one-factorizations of \(K_{5\times 7^{k}+1}\) for any positive integer k.

If n is not divisible by 5, we have \(n=3^ap_1^{\alpha _1}p_2^{\alpha _2}\cdots p_k^{\alpha _k}\) where all \(p_i>5\) are distinct primes and \(a\not \in \{1,2\}\). By Corollary 1 and Theorem 10, there is a pair of orthogonal \(C_4\)-free one-factorizations of \(K_{3^a+1}\) and \(K_{p_i^{\alpha _i}+1}\) for \(a>2\) and each \(p_i>7\) is a non-Fermat prime. Since there is a pair of orthogonal \(C_4\)-free one-factorizations of \(K_{p_i^{\alpha _i}+1}\) for prime \(p_i\ge 7\) and positive integer \(\alpha _i\), by applying Theorems 12 and 8, there is a pair of orthogonal \(C_4\)-free one-factorizations of \(K_{n+1}\).

If n is divisible by 25, we have \(n=3^a5^bp_1^{\alpha _1}p_2^{\alpha _2}\cdots p_k^{\alpha _k}\) where all \(p_i>5\) are distinct primes, \(b\ge 2\) and \(a\not \in \{1,2\}\). By Theorem 10, there is a pair of orthogonal \(C_4\)-free one-factorizations of \(K_{5^{b}+1}\). By applying Theorem 12 with the known pair of orthogonal \(C_4\)-free one-factorizations of \(K_{5^{a},5^{a}}\) in Theorem 8 and a pair of orthogonal \(C_4\)-free one-factorizations of \(K_{3^ap_1^{\alpha _1}p_2^{\alpha _2}\cdots p_k^{\alpha _k}+1}\), there is a pair of orthogonal \(C_4\)-free one-factorizations of \(K_{n+1}\).

If n is divisible by 35 and n is not divisible by 25, we have \(n=3^a\cdot 5\cdot 7^sp_2^{\alpha _2}\cdots p_k^{\alpha _k}\), where \(p_i\ge 11\), \(s\ge 1\) and \(a\not \in \{1,2\}\). From above, there is a pair of orthogonal \(C_4\)-free one-factorizations of \(K_{5\times 7^{b}+1}\). By applying Theorem 12 with the known pair of orthogonal \(C_4\)-free one-factorizations of \(K_{5\times 7^{b},5\times 7^{b}}\) in Theorem 8 and a pair of orthogonal \(C_4\)-free one-factorizations of \(K_{3^ap_2^{\alpha _2}\cdots p_k^{\alpha _k}+1}\), there is a pair of orthogonal \(C_4\)-free one-factorizations of \(K_{n+1}\).

If n is divisible by 5 and n is not divisible by 175, we have \(n=3^a\cdot 5\cdot p_1^{\alpha _1}\cdots p_k^{\alpha _k}\), where \(p_i\ge 11\) and \(a\not \in \{1,2\}\). Since \(5p_1^{\alpha _1}p_2^{\alpha _2}\cdots p_k^{\alpha _k}\ge 7\), we can let \({\alpha _1} \ge 1\). Since each \(p_i\) is a non-Fermat prime, from the proof of Corallary 1 there is a strong starter \(S_w\) in \(GF(p_i)\) satisfying the conditions of Theorem 11. Thus, there is a pair of orthogonal \(C_4\)-free one-factorizations of \(K_{5p_1+1}\). By applying Theorem 12 with the known pair of orthogonal \(C_4\)-free one-factorizations of \(K_{5p_1,5p_1}\) in Theorem 8 and a pair of orthogonal \(C_4\)-free one-factorizations of \(K_{3^ap_1^{\alpha _1-1}\cdots p_k^{\alpha _k}+1}\), there is a pair of orthogonal \(C_4\)-free one-factorizations of \(K_{n+1}\). This completes the proof. \(\square \)

5 Conclusion

In this paper, we consider the constructions of two orthogonal \(C_4\)-free one-factorizations of \(K_{n}\), which can be used to improve the upper bound for two-round rainbow colorings of \(K_n\). Although some constructions of two orthogonal one-factorizations of \(K_{n}\) have been modified successfully, the existence of two orthogonal \(C_4\)-free one-factorizations of \(K_{n}\) is not completely resolved. A further interesting problem is the existence of two orthogonal totally\(C_4\)-free one-factorizations of \(K_{n}\).