×

The solution of the bipartite analogue of the Oberwolfach problem. (English) Zbl 0765.05080

The Oberwolfach problem, as proposed by G. Ringel in 1967 (cf., e.g., R. K. Guy [Unsolved combinatorial problems, Combinat. Math. Appl., Proc. Conf. math. Inst. Oxford 1969, 121-127 (1971; Zbl 0221.05003)]) asks whether it is possible to decompose the complete graph \(K_{2m+1}\) into \(m\) 2-regular factors, each isomorphic to a given 2- regular factor \(F\). It has been conjectured that the answer is “yes” unless \(F\) is isomorphic to \(C_ 4\cup C_ 5\) or to \(C_ 3\cup C_ 3\cup C_ 5\) in which cases the answer is known to be “no”. In the present paper, the author completely solves the bipartite variant of the problem: If \(F\) is a 2-regular graph consisting of a disjoint union of cycles of lengths \(a_ 1,\dots,a_ s\) \((a_ i\geq 3)\) then the complete bipartite graph \(K_{n,n}\) can be decomposed into factors isomorphic to \(F\) if and only if \(n\) and all \(a_ i\)’s are even integers, \(\Sigma a_ i=2n\), and \(F\) is not isomorphic to \(C_ 6\cup C_ 6\). The method used is that of so-called pathlike factorizations. An application of the method to the original Oberwolfach problem yields the following theorem: If \(t,a_ 0,a_ 1,\dots,a_ k\) are integers with \(t\geq 1\), \(k\geq 0\), \(a_ i>(2t+1)(4t+1)\) and \(n=\Sigma a_ i\equiv 2t+3\pmod{4t+4}\) then the complete graph \(K_ n\) can be decomposed into factors isomorphic to \(C_{a_ 0}\cup C_{a_ 1}\cup\cdots\cup C_{a_ k}\).
Reviewer: D.Fronček

MSC:

05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

Citations:

Zbl 0221.05003
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alspach, B.; Häggkvist, R., Some observations on the Oberwolfach problem, Graph Theory, 9, 177-187 (1985) · Zbl 0603.05032
[2] Bose, R. C.; Shrikhande, S. S.; Parker, E. T., Further results on the construction of mutually orthogonal latin squares and the falsity of Euler’s conjecture, Canad. J. Math., 12, 189-203 (1960) · Zbl 0093.31905
[3] Guy, R. K., Unsolved combinatorial problems, (Welsh, D., Combinatorial Mathematics and its Applications (1971), Academic Press: Academic Press New York), 121-127
[4] Häggkvist, R., A lemma on cycle decompositions, (Alspach, B. R.; Godsil, C. D., Cycles in Graphs, Ann. Discrete Math., 27 (1985), North-Holland: North-Holland Amsterdam), 227-232
[5] Häggkvist, R., Decompositions of complete bipartite graphs, London Math. Soc. Lecture Notes, 141, 115-147 (1989)
[6] Piotrowski, W. L., Untersuchungen über das Oberwolfacher Problem (1979), manuscript.
[7] Tarry, G., Le probléme des 36 officiers, C.R. Assoc. France Av. Sci., 29, 2, 170-203 (1900) · JFM 32.0219.04
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.