# A Discrete Logarithm Construction for Orthogonal Double Covers of the Complete Graph by Hamiltonian Paths
**Authors**: M. A. Ollis
## Abstract
During their investigation of power-sequence terraces, Anderson and Preece briefly mention a construction of a terrace for the cyclic group $\mathbb{Z}_{n}$ when $n$ is odd and $2n+1$ is prime; it is built using the discrete logarithm modulo $2n+1$ . In this short note we see that this terrace gives rise to an orthogonal double cover (ODC) for the complete graph $K_{n}$ by Hamiltonian paths. This gives infinitely many new values for which such an ODC is known.
Keywords and phrases: cyclic group, discrete logarithm, orthogonal double cover, symmetric sequencing, terrace.
MSC2020: 05B40, 05C25, 05C70.
## 1 Introduction
Let $G$ be a graph with $n$ vertices. An orthogonal double cover (ODC) of the complete graph $K_{n}$ by $G$ is a collection $\mathcal{G}=\{G_{i}\cong G:1\leq i\leq n\}$ that satisfies the following two properties:
1. Double Cover Property: Each edge of $K_{n}$ lies in exactly two graphs in $\mathcal{G}$ .
1. Orthogonality Property: Any two distinct graphs in $\mathcal{G}$ have exactly one edge in common.
If $K_{n}$ has an ODC by $G$ then $G$ has exactly $n-1$ edges. Figure 1 gives an example of an ODC of $K_{9}$ by Hamiltonian paths.
Figure 1: An orthogonal double cover of $K_{9}$ by Hamiltonian paths.
$$
\begin{array}[]{c}(0,1,4,2,7,5,6,3,8)\\
(1,2,5,3,8,6,7,4,0)\\
(2,3,6,4,0,7,8,5,1)\\
(3,4,7,5,1,8,0,6,2)\\
(4,5,8,6,2,0,1,7,3)\\
(5,6,0,7,3,1,2,8,4)\\
(6,7,1,8,4,2,3,0,5)\\
(7,8,2,0,5,3,4,1,6)\\
(8,0,3,1,6,4,5,2,7)\end{array}
$$
Orthogonal double covers have a variety of applications. See the survey paper [7] for a discussion of these and of the history and development of the problem. In this note we are concerned with the case when $G$ is a Hamiltonian path and $n$ is odd. This is a case both of independent interest and of application to the almost-Hamiltonian cycle case, one of the original motivators for the study of ODCs. Theorem 1.1 captures the current state of knowledge with these constraints.
**Theorem 1.1**
*Let $n$ be odd with $n>1$ . The complete graph $K_{n}$ has an ODC by Hamiltonian paths when it is possible write $n=ab$ , where:
- $a$ has one of the forms $(k^{2}+1)/2$ , $k^{2}$ or $k^{2}+1$ for some integer $k$ , or
$$
a\in\{3,7,11,15,19,21,33,57,69,77,93\},
$$
- $b=1$ or $b=q_{1}q_{2}\cdots q_{m}$ for not-necessarily-distinct prime powers $q_{i}\equiv 1\pmod{4}$ , with each $q_{i}$ either of one of the forms $(k^{2}+1)/2$ , $k^{2}$ or $k^{2}+1$ for some integer $k$ , or prime with $q_{i}<10^{5}$ .*
* Proof note*
Given an ODC of $K_{a}$ by Hamiltonian paths (or the trivial case $a=1$ ), we may combine this with a “2-colorable” ODC for $K_{q}$ by Hamiltonian paths, where $q$ is a prime power congruent to $1\pmod{4}$ , to obtain an ODC of $K_{aq}$ by Hamiltonian paths. In the statement of the theorem, the values of $q_{i}$ are those for which such a 2-colorable ODC is known. There is an ODC of $K_{a}$ by Hamiltonian paths for each of the non-trivial values of $a$ and, in conjunction with the possibilities for $b$ , the statement covers all odd values $n$ for which ODCs of $K_{n}$ by Hamiltonian paths are known. For the full definitions and constructions that prove this result, see [7, 8] and the references therein. ∎
A “terrace”, to be defined in the next section for the cases we need, is an arrangement of the elements of a group such that adjacent elements have particular difference/quotient properties. Terraces for arbitrary groups were formally introduced by Bailey in 1984 [6]. However, the concept for cyclic groups (which is all we require in this note) is implicit in work of Williams in 1949 [14] and, arguably, in that of Lucas and Walecki in 1892, see [1].
A terrace for a group of order $n$ gives rise to collection of $n$ Hamiltonian paths in the complete graph $K_{n}$ that has the double cover property (equivalently, a row quasi-complete latin square of order $n$ ) [6]. A terrace may have additional properties that mean we in fact have an orthogonal double cover of $K_{n}$ by Hamiltonian paths [3, 9, 10]. These additional properties are rare and it seems to be a difficult problem to find terraces that have them.
In [4], the first in a series of papers investigating “power-sequence terraces” for cyclic groups (see [5] for references for the full series), Anderson and Preece give a construction for a terrace of $\mathbb{Z}_{n}$ using discrete logarithms modulo $2n+1$ that applies when $n$ is odd and $2n+1$ is prime. In the next section we prove that this terrace has the additional properties required to give an ODC of $K_{n}$ by Hamiltonian paths.
We are thus able to augment the list of values of $n$ for which $K_{n}$ is known to have an ODC by Hamiltonian paths as follows.
**Theorem 1.2**
*If $n$ is odd and $2n+1$ is prime, then $K_{n}$ has an orthogonal double cover by Hamiltonian paths.*
Any value of $n$ that satisfies the conditions of Theorem 1.2 may be added as a possibility for $a$ in Theorem 1.1. Each new value that is congruent to $3\pmod{4}$ gives rise to infinitely many new values for which an ODC of the complete graph by Hamiltonian paths is known. These are straightforward to describe: for each prime $p$ with $p\equiv 7\pmod{8}$ we obtain the value $(p-1)/2$ , which is a new value when $p\geq 47$ and $(p-1)/2$ is not of one of the forms $(k^{2}+1)/2$ , $k^{2}$ or $k^{2}+1$ for some integer $k$ .
Given the possibilities for $b$ in Theorem 1.1, values given by Theorem 1.2 that are congruent to $1\pmod{4}$ do not immediately cover as many new cases.
If the value of $n$ is prime (in which case it is a Sophie Germain prime) and it is not of one of the forms $(k^{2}+1)/2$ or $k^{2}+1$ for some integer $k$ , then it gives infinitely many new values with $n\equiv 1\pmod{4}$ (provided $n>10^{5}$ ) and $n\equiv 3\pmod{4}$ (provided $n>20$ ). Sophie Germain primes are well-studied and many such are known. See, for example, [13, A005384] and the linked files.
We also get values congruent to $1\pmod{4}$ , each corresponding to a infinite family, by taking $n$ to be the product of an even number of distinct primes, each congruent to $3\pmod{4}$ (subject, of course, to $2n+1$ being prime). These are new when $n>100$ and is not of the form $(k^{2}+1)/2$ or $k^{2}+1$ for some integer $k$ .
## 2 The Construction
We shall work in $\mathbb{Z}_{n}=\{0,1,\ldots,n-1\}$ , the additively-written cyclic group of order $n$ . In this section, $n$ is always odd; write $n=2m+1$ . When we consider the complete graph $K_{n}$ , it is convenient to consider it as having its vertices labeled with the elements of $\mathbb{Z}_{n}$ .
Define the length of the edge between vertices $x$ and $y$ to be $\{y-x,x-y\}$ . For brevity, we sometimes abbreviate this to $\pm(y-x)$ . Let $\mathbf{h}$ be a Hamiltonian path in $K_{n}$ . If each edge length $\pm\ell$ for $\ell\in\{1,2,\ldots,m\}$ occurs exactly twice in $\mathbf{h}$ then $\mathbf{h}$ is a terrace for $\mathbb{Z}_{n}$ [6].
Define the distance between two edges $e_{1}=(x_{1},y_{1})$ and $e_{2}=(x_{2},y_{2})$ of the same length to be $\pm k$ if either
$$
\{x_{1}+k,y_{1}+k\}=\{x_{2},y_{2}\}\textrm{ \ or \ }\{x_{1}-k,y_{1}-k\}=\{x_{2},y_{2}\}.
$$
If a terrace $\mathbf{h}$ has the property that every possible distance $\pm k$ , for $k\in\{1,2,\ldots,m\}$ , appears between the pairs of edges of the same length, then $\mathbf{h}$ is an ODC-starter for $\mathbb{Z}_{n}$ [9, 10].
**Lemma 2.1**
*[9, 10] If $\mathbf{h}$ is an ODC-starter in $K_{n}$ , then the translates of $\mathbf{h}$ form an orthogonal double cover of $K_{n}$ by Hamiltonian paths.*
**Example 2.2**
*Let $n=9$ and consider the Hamiltonian path $\mathbf{h}=(0,1,4,2,7,5,6,3,8)$ in $K_{9}$ . This is a terrace; the sequence of edge lengths is
$$
(\pm 1,\pm 3,\pm 2,\pm 4,\pm 2,\pm 1,\pm 3,\pm 4).
$$
Further, it is a ODC-starter. The distances associated with the edge lengths $\pm 1$ , $\pm 2$ , $\pm 3$ and $\pm 4$ are $\pm 4$ , $\pm 3$ , $\pm 2$ and $\pm 1$ respectively. Hence, by Lemma 2.1, the translates of $\mathbf{h}$ are an orthogonal double cover of $K_{9}$ by Hamiltonian paths; this is the ODC displayed in Figure 1.*
Here is Anderson and Preece’s complete discussion of their construction in [4] (citation updated to align with the numbering of the present paper):
…there is also a general Galois field construction for $\mathbb{Z}_{n}$ terraces for any odd integer $n$ such that $2n+1$ is prime; some of the mathematics for this is in [12]. Let $x$ be a primitive root of $\mathbb{Z}_{2n+1}$ . Working in $\mathbb{Z}_{2n+1}$ , obtain the quantities $c_{i}$ ( $i=1,2,\ldots,n$ ) defined by $x^{c_{i}}=i$ . Now reduce $c_{i}$ modulo $n$ , to give $d_{i}$ ( $i=1,2,\ldots,n$ ). Then $(d_{1},d_{2},\ldots,d_{n})$ is a $\mathbb{Z}_{n}$ terrace. With $n=5$ and $x=2$ we obtain the $\mathbb{Z}_{5}$ terrace $(0,1,3,2,4)$ , and with $n=9$ and $x=2$ we obtain the $\mathbb{Z}_{9}$ terrace $(0,1,4,2,7,5,6,3,8)$ .
We shall prove Theorem 1.2 by showing that not only is Anderson and Preece’s discrete logarithm construction a terrace (Theorem 2.3), it is also an ODC-starter (Theorem 2.4). Notice that Example 2.2 verifies this for the case given with $n=9$ and $x=2$ .
Here is some notation, which will hold for the remainder of the paper. Let $g$ be a primitive root of $\mathbb{Z}_{2n+1}$ , where $n$ is odd. We take an element $x\in\mathbb{Z}_{2n+1}$ to $\widehat{\log_{g}(x)}\in\mathbb{Z}_{n}$ in two steps, where the first is the discrete logarithm $\log_{g}$ with respect $g$ and lies in $\mathbb{Z}_{2n}$ and the second is the natural projection $\mathbb{Z}_{2n}\rightarrow\mathbb{Z}_{n}$ , which we denote in general by $y\mapsto\widehat{y}$ . Then Anderson and Preece’s construction is given by ${\bf d}_{g}=(d_{1},d_{2},\ldots,d_{n})$ , where $d_{i}=\widehat{\log_{g}(i)}$ for each $i$ .
We need one more concept before the results. Let ${\bf a}=(a_{1},a_{2},\ldots,a_{2n})$ be an arrangement of the elements of $\mathbb{Z}_{2n}$ and let $b_{i}=a_{i+1}-a_{i}$ for $i$ in the range $1\leq i<2n$ . If the elements $b_{i}$ are all of the non-zero elements of $\mathbb{Z}_{n}$ and $b_{i}=-b_{2n-i}$ for $i$ in the range $1\leq i<n-1$ then ${\bf a}$ is a symmetric directed terrace for $\mathbb{Z}_{2n}$ and the sequence $(b_{1},b_{2},\ldots,b_{2n-1})$ is a symmetric sequencing. In [2] it is shown that if $(a_{1},a_{2},\ldots,a_{2n})$ is a symmetric directed terrace then $(\widehat{a_{1}},\widehat{a_{2}},\ldots,\widehat{a_{n}})$ is a terrace. (This concept, and result, works more generally in groups that have exactly one involution, and it is always possible to go from the terrace to a symmetric sequencing; see, for example, [11].)
**Theorem 2.3**
*Anderson and Preece’s discrete logarithm construction gives a terrace for each odd $n$ such that $2n+1$ is prime.*
* Proof*
It is sufficient to show that the sequence ${\bf c}_{g}=(c_{1},c_{2},\ldots,c_{2n})$ given by $c_{i}=\log_{g}(i)$ is a symmetric directed terrace for $\mathbb{Z}_{2n}$ . Let $b_{i}=c_{i+1}-c_{i}$ for $i$ in the range $1\leq i<2n$ . As $g$ is a primitive root, when $1\leq i,j\leq 2n$ with $i\neq j$ we have
$$
c_{i}=\log_{g}(i)\neq\log_{g}(j)=c_{j}
$$
and so ${\bf c}_{g}$ is an arrangement of the elements of $\mathbb{Z}_{2n}$ . The difference $b_{i}$ is given by
$$
b_{i}=\log_{g}(i+1)-\log_{g}(i)=\log_{g}\left(\frac{i+1}{i}\right).
$$
When $1\leq i,j\leq 2n$ with $i\neq j$ , we have $(i+1)/i\neq(j+1)/j$ in $\mathbb{Z}_{2n+1}$ and hence $b_{i}\neq b_{j}$ in $\mathbb{Z}_{2n}$ . Let $1\leq i<n$ . In $\mathbb{Z}_{2n+1}$ we have
$$
\frac{2n-i+1}{2n-i}=\frac{i}{i+1}=\left(\frac{i+1}{i}\right)^{-1}.
$$
Therefore, in $\mathbb{Z}_{2n}$ ,
$$
b_{2n-i}=\log_{g}\left(\frac{2n-i+1}{2n-i}\right)=\log_{g}\left(\left(\frac{i+1}{i}\right)^{-1}\right)=-\log_{g}\left(\frac{i+1}{i}\right)=-b_{i}.
$$ Hence ${\bf c}_{g}$ is a symmetric directed terrace for $\mathbb{Z}_{2n}$ and ${\bf d}_{g}$ is a terrace for $\mathbb{Z}_{n}$ . ∎
**Theorem 2.4**
*Anderson and Preece’s discrete logarithm construction gives an ODC-starter for each odd $n$ such that $2n+1$ is prime.*
* Proof*
Theorem 2.3 shows that Anderson and Preece’s discrete logarithm construction ${\bf d}_{g}$ is a terrace. It remains to show that between the pairs of edges of the same length we realise all possible distances. Recall that $n=2m+1$ . Fix $k$ in the range $1\leq k\leq m$ . We want to show that there is a pair of edges of the same length that are at distance $\pm k$ . Let $x=g^{k}$ in $\mathbb{Z}_{2n+1}$ and let $u=(1-x)/(1+x)$ , which is well-defined as $x=-1$ only when $k=n=2m+1$ . Let $i=(u-1)^{-1}$ and $j=xi$ in $\mathbb{Z}_{2n+1}$ . The pairs $(i,i+1)$ and $(j,j+1)$ in $\mathbb{Z}_{2n+1}$ become the edges
$$
e_{i}=\{\widehat{\log_{g}(i)},\widehat{\log_{g}(i+1)}\}\text{ \ \ and \ \ }e_{j}=\{\widehat{\log_{g}(j)},\widehat{\log_{g}(j+1)}\}
$$
in the terrace for $\mathbb{Z}_{n}$ . We claim that these edges have the same length and are at distance $\pm k$ . As $i=(u-1)^{-1}$ , we have $i^{-1}=u-1$ and can evaluate
$$
\frac{i+1}{i}=1+\frac{1}{i}=1+(u-1)=u
$$
in $\mathbb{Z}_{2n+1}$ . As $j=xi$ and writing $u-1$ in terms of $x$ as $-2x/(1+x)$ we also have
$$
\frac{j+1}{j}=1+\frac{1}{xi}=1+\frac{u-1}{x}=\frac{x-1}{1+x}=-u
$$
in $\mathbb{Z}_{2n+1}$ . In $\mathbb{Z}_{2n+1}$ , we have $g^{n}=-1$ and so in $\mathbb{Z}_{n}$ we have $\widehat{\log_{g}(y)}=\widehat{\log_{g}(-y)}$ for all $y$ . In particular, the lengths of $e_{i}$ and $e_{j}$ are both $\widehat{\log_{g}(u)}=\widehat{\log_{g}(-u)}$ . We now show that $e_{1}$ and $e_{2}$ are at distance $\pm k$ . First, since $j=xi=g^{k}i$ , we have
$$
\widehat{\log_{g}(i)}+k=\widehat{\log_{g}(j)}
$$
in $\mathbb{Z}_{n}$ . Second, note that $j+1=-x(i+1)$ in $\mathbb{Z}_{2n+1}$ , hence
$$
\log_{g}(j+1)=\log_{g}(-1)+k+\log(i+1)=n+k+\log(i+1)
$$
in $\mathbb{Z}_{2n}$ . This gives
$$
\widehat{\log_{g}(j+1)}=\widehat{\log_{g}(i+1)}+k
$$
in $\mathbb{Z}_{n}$ , and so the edges are indeed at distance $\pm k$ . Therefore, Anderson and Preece’s discrete logarithm construction has all the properties required to be an ODC-starter. ∎
An orthogonal double cover of $K_{n}$ by Hamiltonian paths, where $n$ is odd and $2n+1$ is prime, now exists by Lemma 2.1. This proves Theorem 1.2.
**Example 2.5**
*Let $n=15$ . Then $2n+1=31$ , which is prime and has 3 as a primitive root. Using this, the Anderson and Preece discrete logatirhm construction gives the following ODC-starter in $\mathbb{Z}_{15}$ :
$$
(0,9,1,3,5,10,13,12,2,14,8,4,11,7,6).
$$
Its sequence of edge lengths is
$$
(\pm 6,\pm 7,\pm 2,\pm 2,\pm 5,\pm 3,\pm 1,\pm 5,\pm 3,\pm 6,\pm 4,\pm 7\pm 4,\pm 1).
$$
The distances between the pairs of edges of lengths $\pm 1,\pm 2,\ldots,\pm 7$ are
$$
\pm 6,\pm 2,\pm 4,\pm 3,\pm 7,\pm 1,\pm 5
$$
respectively.*
## References
- [1] B. Alspach, The wonderful Walecki construction. Bulletin of the I.C.A. 52 (2008) 7–20.
- [2] B. A. Anderson, Sequencings and starters, Pacific J. Math. 64 (1976) 17–24.
- [3] B. A. Anderson and P. A. Leonard, A class of self-orthogonal 2-sequencings, Des. Codes Cryptography 1 (1991) 149–181.
- [4] I. Anderson and D. A. Preece, Power-sequence terraces for $\mathbb{Z}_{n}$ where $n$ is an odd prime power, Discrete Math. 261 (2003) 31–58.
- [5] I. Anderson, M. A. Ollis and D. A. Preece. On power-sequence and matryoshka terraces for $\mathbb{Z}_{n}$ . Bulletin of the I.C.A. 81 (2017) 98–117.
- [6] R. A. Bailey, Quasi-complete Latin squares: construction and randomisation, J. Royal Statist. Soc. B 46 (1984) 323–334.
- [7] H. D. O. Gronau, M. Grüttmüller, S. Hartmann, U. Leck and V. Leck, On orthogonal double covers of graphs. Des. Codes Cryptogr. 27 (2002) 49–91.
- [8] S. Hartmann, U. Leck and V. Leck, More orthogonal double covers of complete graphs by Hamiltonian paths, Discrete Math. 308 (2008) 2502–2508.
- [9] J. D. Horton and G. M. Nonay, Self-orthogonal Hamilton path decompositions, Discrete Math. 97 (1991) 251–264
- [10] V. Leck, On orthogonal double covers by Hamilton paths, Congr. Numer. 135 (1998) 153–157.
- [11] M. A. Ollis, Sequenceable groups and related topics, Electron. J. Combin., DS10 (2002, updated 2025).
- [12] D. A. Preece, B. J. Vowden, R. Hughes Jones, C. A. Rodger, C. J. Vowden, Choreographing designs, Math. Sci. 20 (1995) 15–32.
- [13] N. J. A. Sloane (Ed.), The On-Line Encyclopedia of Integer Sequences (2025) https://oeis.org.
- [14] E. J. Williams, Experimental designs balanced for the estimation of residual effects of treatments, Aust. J. Scient. Res. A, 2 (1949) 149–168.