×

zbMATH — the first resource for mathematics

Cyclic (0,1)-factorizations of the complete graph. (English) Zbl 0686.05040
It is well-known [see T. J. Folkman and D. R. Fulkerson, Edge-colorings in bipartite graphs, Combin. Math. Appl., Proc. Conf. Univ. North Carolina 1967, 561-577 (1969; Zbl 0204.570)] that \(K_ n\) admits an edge-decomposition into matchings of size k. Such a decomposition is said to be cyclic if there is a cyclic permutation of the vertices of \(K_ n\) which preserves the mappings.
The author proves that if \(n>0\) and \(0<k<\frac{n}{2}\) and \(\left( \begin{matrix} n\\ 2\end{matrix} \right)\equiv 0 (mod k)\) then \(K_ n\) has a cyclic decomposition into matchings of size k.
This complements a result of A. Hartman and A. Rosa [Cyclic one-factorizations of the complete graph, Eur. J. Comb. 6, 45-48 (1985; Zbl 0624.05051)] and provides a ‘perfect covering’ of \(K_ n\vee \bar K_ m\) where \(m=n(n-1)/2k\).
Reviewer: K.R.Parthasarathy

MSC:
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
PDF BibTeX XML Cite