×

Constructions of perfect Mendelsohn designs. (English) Zbl 0756.05012

Let \(n\) and \(k\) be positive integers. An \((n,k,1)\)-Mendelsohn design is an ordered pair \((V,{\mathcal C})\) where \(V\) is the vertex set of \(D_ n\), the complete directed graph on \(n\) vertices, and \({\mathcal C}\) is a set of directed cycles (called blocks) of length \(k\) which form an arc-disjoint decomposition of \(D_ n\). An \((n,k,1)\)-Mendelsohn design is called a perfect design and denoted briefly by \((n,k,1)\)-PMD if for any \(r\), \(1\leq r\leq k-1\), and for each \((x,y)\in V\times V\) there is exactly one cycle \(c\in{\mathcal C}\) in which the (directed) distance along \(c\) from \(x\) to \(y\) is \(r\). A necessary condition for the existence of an \((n,k,1)\)-PMD is \(n(n-1)\equiv 0\pmod k\). In this paper some new techniques used in the construction of PMD’s, including constructions of the product type, are described. As an application, it is shown that the necessary condition for the existence of an \((n,5,1)\)-PMD is also sufficient, except for \(n=6\) and with at most 21 possible exceptions of \(n\) of which 286 is the largest.
Reviewer: R.N.Mohan (Nuzvid)

MSC:

05B05 Combinatorial aspects of block designs
05B07 Triple systems
05B30 Other designs, configurations
Full Text: DOI

References:

[1] Baker, R. D., An elliptic semiplane, J. Combin. Theory Ser. A, 25, 193-195 (1978) · Zbl 0433.05017
[2] Bennett, F. E., Conjugate orthogonal Latin squares and Mendelsohn designs, Ars Combin., 19, 51-62 (1985) · Zbl 0577.05016
[3] Bennett, F. E.; Mendelsohn, E.; Mendelsohn, N. S., Resolvable perfect cyclic designs, J. Combin. Theory Ser. A, 29, 140-150 (1980) · Zbl 0444.05021
[4] Bennett, F. E.; Zhang, X.; Zhu, L., Perfect Mendelsohn designs with block size four, Ars Combin., 29, 65-72 (1990) · Zbl 0717.05020
[5] Beth, T.; Jungnickel, D.; Lenz, H., Design Theory (1985), Bibliographisches Institut: Bibliographisches Institut Zürich · Zbl 0569.05002
[6] Brouwer, A. E., Four MOLS of order 10 with a hole of order 2, J. Statist. Plann. Inference, 10, 203-205 (1984) · Zbl 0553.05022
[7] Brouwer, A. E., The number of mutually orthogonal Latin squares-a table up to order 10000, (Research Report ZW123/79 (1979), Mathematisch Centrum: Mathematisch Centrum Amsterdam) · Zbl 0405.05013
[8] Dénes, J.; Keedwell, A. D., Latin Squares and Their Applications (1974), Academic Press: Academic Press New York · Zbl 0283.05014
[9] Hsu, D. F.; Keedwell, A. D., Generalized complete mappings, neofields, sequenceable groups and block designs, II. Pacific J. Math., 117, 291-312 (1985) · Zbl 0575.05011
[10] Lindner, C. C.; Stinson, D. R., Steiner pentagon systems, Discrete Math., 52, 67-74 (1984) · Zbl 0549.05010
[11] Mendelsohn, N. S., A natural generalization of Steiner triple systems, (Atkin, A. O.L.; Birch, B. J., Computers in Number Theory (1971), Academic Press: Academic Press New York), 323-338 · Zbl 0216.30102
[12] Mendelsohn, N. S., Perfect cyclic designs, Discrete Math., 20, 63-68 (1977) · Zbl 0369.05015
[13] Mullin, R. C.; Zhu, L., The spectrum of HSOLSSOM \((h^n)\) where \(h\) is odd, Utilitas Math., 27, 157-168 (1985) · Zbl 0597.05014
[14] Roth, R.; Peters, M., Four pairwise orthogonal Latin squares of order 24, J. Combin. Theory Ser. A, 44, 152-155 (1987) · Zbl 0605.05006
[15] Stinson, D. R., A short proof of the non-existence of a pair of orthogonal Latin squares of order 6, J. Combin. Theory Ser. A, 36, 373-376 (1984) · Zbl 0538.05012
[16] Stinson, D. R.; Zhu, L., On sets of three MOLS with holes, Discrete Math., 54, 321-328 (1985) · Zbl 0572.05017
[17] Todorov, D. T., Three mutually orthogonal Latin squares of order 14, Ars Combin., 20, 45-48 (1985) · Zbl 0596.05009
[18] Todorov, D. T., Four mutually orthogonal Latin squares of order 20, Ars Combin., 27, 63-65 (1989) · Zbl 0675.05012
[19] Wallis, W. D., Three orthogonal Latin squares, Congr. Numer., 42, 69-86 (1984) · Zbl 0546.05011
[20] Wilson, R. M., A few more squares, Proc. 5th S-E Conf. on Combinatorics, Graph Theory, and Computing, 675-680 (1974) · Zbl 0326.05016
[21] Wilson, R. M., Concerning the number of mutually orthogonal Latin squares, Discrete Math., 9, 181-198 (1974) · Zbl 0283.05009
[22] Wilson, R. M., Constructions and uses of pairwise balanced designs, Math. Centre Tracts, 55, 18-41 (1974) · Zbl 0312.05010
[23] Zhang, X., On the existence of \((v, 4, 1)\)-PMD, Ars Combin., 29, 3-12 (1990) · Zbl 0749.05016
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.