×

Resolvable and near-resolvable decompositions of \(DK_ v\) into oriented 4-cycles. (English) Zbl 0779.05034

This paper deals with decompositions of complete digraphs into a spanning set of factors, each of which is a vertex-disjoint union of isomorphic oriented 4-cycles. Necessary and sufficient conditions are given for the existence of such decompositions for three orientations of the 4-cycle (those for the other orientation have already appeared in the literature). The authors also consider decompositions in which each factor spans all but one of the vertices of the complete digraph, and give necessary and sufficient conditions for the three orientations of the 4-cycle for which the problem was unsolved.

MSC:

05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
PDFBibTeX XMLCite
Full Text: DOI EuDML

References:

[1] Bermond, J. C.,Decomposition of K n * into k-circuits and balanced G-designs. In Recent Advances in Graph Theory (ed. M. Fielder), Proc. Symp., Prague 1975, pp. 57–68. · Zbl 0336.05020
[2] Bermond, J. C., Germa, A. andSotteau, D.,Resolvable decomposition of K n * . J. Combinatorial Th. Ser. A26 (1979), 179–185. · Zbl 0411.05027 · doi:10.1016/0097-3165(79)90067-0
[3] Bermond, J. C. andFaber, V.,Decomposition of the complete directed graph into k-circuits. J. Combinatorial Th. Ser. B21 (1976), 146–155. · Zbl 0344.05123 · doi:10.1016/0095-8956(76)90055-1
[4] Bennett, F. E. andSotteau, D.,Almost resolvable decomposition of K n * . J. Combinatorial Th. Ser. B30 (1981), 228–232. · Zbl 0509.05042 · doi:10.1016/0095-8956(81)90067-8
[5] Bennett, F. E. andZhang, X.,Resolvable Mendelsohn designs with block size 4. Aequationes Math.40 (1990), 248–260. · Zbl 0725.05012 · doi:10.1007/BF02112298
[6] Harary, F., Wallis, W. D. andHeinrich, K.,Decompositions of complete symmetric digraphs into the four oriented quadrilateralsm. InCombinatorial Mathematics, Proceedings of the International Conference on Combinatorial Theory, Canberra, 1977. (D. A. Holton, Jennifer Seberry, eds.), Springer-Verlag, New York, 1977, pp. 165–173.
[7] Hung, H. Y. andMendelsohn, N. S.,Directed triple systems. J. Combinatorial Th. Ser. A14 (1973), 310–318. · Zbl 0263.05020 · doi:10.1016/0097-3165(73)90007-1
[8] Mendelsohn, N. S.,A natural generalization of Steiner triple systems. InComputers in Number Theory, Proc. Sci. Res. Council Atlas Sympos. No. 2, Oxford 1969. Academic Press, London, 1971, pp. 323–338.
[9] Schönheim, J.,Partition of the edges of the directed complete graph into 4-cycles. Discrete Math.11 (1975), 67–70. · doi:10.1016/0012-365X(75)90105-3
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.