Black 1-factors and Dudeney sets

Abstract

A set of Hamilton cycles in the complete graph $K_n$ is called a Dudeney set if every path of length two lies on exactly one of the cycles. It has been conjectured that there is a Dudeney set for every complete graph. It is known that there exists a Dudeney set for $K_n$ when $n$ is even, but the question is still unsettled when $n$ is odd.

In this paper, we define a black $1$-factor in $K_{p+1}$ for an odd prime $p$, and show that if there exists a black $1$-factor in $K_{p+1}$, then we can construct a Dudeney set for $K_{p+2}$. We also show that if there is a black $1$-factor in $K_{p+1}$, then $2$ is a quadratic residue modulo $p$. Using this result, we obtain some new Dudeney sets for $K_n$ when $n$ is odd.