Black 1-factors and Dudeney sets

Midori Kobayashi*, Brendan D. McKay, Nobuaki Mutoh, Gisaku Nakamura

*Corresponding author for this work

    Research output: Contribution to journalArticlepeer-review

    5 Citations (Scopus)

    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 languageEnglish
    Pages (from-to)167-174
    Number of pages8
    JournalJournal of Combinatorial Mathematics and Combinatorial Computing
    Volume75
    Publication statusPublished - Nov 2010

    Fingerprint

    Dive into the research topics of 'Black 1-factors and Dudeney sets'. Together they form a unique fingerprint.

    Cite this