Cycle frames and the Oberwolfach problem

Peer review under responsibility of Kalasalingam University.

Abstract

For an integer $\lambda ,$ $G\left(\lambda \right)$ denotes a graph $G$ with uniform edge-multiplicity $\lambda .$ Let $J$ be a subset of positive integers. A 2-regular subgraph of $m$-partite graph $K_m\otimes I_n$ containing vertices of all but one partite set is called partial 2-factor, where $\otimes$ denotes wreath product and $I_n$ is an independent set on $n$ vertices. If $(K_m\otimes I_n)\left(\lambda \right)$ can be partitioned into edge-disjoint partial 2-factors such that each partial 2-factor consists of cycles of lengths from $J,$ then we say that $(K_m\otimes I_n)\left(\lambda \right)$ has a $(J,\lambda )$-cycle frame. The Oberwolfach problem OP $(m_1^{{\alpha }_1},m_2^{{\alpha }_2},\dots ,m_t^{{\alpha }_t}),$ raised by Ringel, asks the existence of a 2-factorization of $K_n$ (when $n$ is odd) or $K_n-I$ (when $n$ is even), in which each 2-factor consists of exactly ${\alpha }_i$ cycles of length $m_i$, $i=1,2,\dots ,t.$ In this paper, we show that there exists a $(4,6,\lambda )$-cycle frame of $(K_m\otimes I_n)\left(\lambda \right)$ if and only if $\lambda n\equiv 0(mod2)$, $m\ge 3$, $(n,m)\notin (1,3),(2t+1,2s)\mid t\ge 0,s\ge 2$. Further we show that there exists a $(3,4,1)$-cycle frame of $K_m\otimes I_n$ if and only if $m\ge 3$ and $n\equiv 0(mod2).$ As a consequence, we solve OP$(3^a,4^b),$ OP$(3^a,6^b)$ and OP$(5^a,10^b)$ with some restrictions on $a,b\in \mathbb{N}.$

Keywords:

• Decomposition
• Factorization
• Cycle frame

Notes

Peer review under responsibility of Kalasalingam University.