Abstract
A set of Hamilton cycles in the complete graph Kn 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 Kn when n is even, but the question is still unsettled when n is odd. In this paper, we define a black 1-factor in Kp+1 for an odd prime p, and show that if there exists a black 1-factor in Kp+1, then we can construct a Dudeney set for Kp+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 Kn when n is odd.
Original language | English |
---|---|
Pages (from-to) | 167-174 |
Number of pages | 8 |
Journal | Journal of Combinatorial Mathematics and Combinatorial Computing |
Volume | 75 |
Publication status | Published - Nov 2010 |