Constructions of perfect Mendelsohn designs

✍ Scribed by F.E. Bennett; K.T. Phelps; C.A. Rodger; L. Zhu

• Publisher: Elsevier Science
• Year: 1992
• Tongue: English
• Weight: 820 KB
• Volume: 103
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(92)90264-g

✦ Synopsis

of perfect Mendelsohn designs, Discrete Mathematics 103 (1992) 139-151.

Let n and k be positive integers. An (n, k, 1)-Mendelsohn design is an ordered pair (V, %) where V is the vertex set of D,, the complete directed graph on n vertices, and '%' is a set of directed cycles (called blocks) of length k which form an arc-disjoint decomposition of D,,. An (n, k, 1)-Mendelsohn design is called a perfect design and denoted briefly by (n, k, I)-PMD if for any r, 1 G r s k -1, and for each (x, y) E V x V there is exactly one cycle c E V in which the (directed) distance along c from x to y is r. A necessary condition for the existence of an (n, k, I)-PMD is n(n -1) = 0 (mod k). In this paper we shall describe some new techniques used in the construction of PMD's, including constructions of the product type. As an application, we show that the necessary condition for the existence of an (n, 5, l)-PMD is also sufficient, except for n = 6 and with at most 21 possible exceptions of n of which 286 is the largest.