The Directed Oberwolfach Problem With Variable Cycle Lengths: A Recursive Construction

ABSTRACT The directed Oberwolfach problemOP* ( m 1 , … , m k )asks whether the complete symmetric digraphK n *, assumingn = m 1 + ⋯ + m k, admits a decomposition into spanning subdigraphs, each a disjoint union ofkdirected cycles of lengthsm 1 , … , m k. We hereby describe a method for constructing a solution toOP* ( m 1 , … , m k )given a solution toOP* ( m 1 , … , m ℓ ), for someℓ < k, if certain conditions onm 1 , … , m kare satisfied. This approach enables us to extend a solution forOP* ( m 1 , … , m ℓ )into a solution forOP* ( m 1 , … , m ℓ , t ), as well as into a solution forOP* ( m 1 , … , m ℓ , 2 〈 t 〉), where2 〈 t 〉denotestcopies of 2, providedtis sufficiently large. In particular, our recursive construction allows us to effectively address the two‐table directed Oberwolfach problem. We show thatOP* ( m 1 , m 2 )has a solution for all2 ≤ m 1 ≤ m 2, with a definite exception ofm 1 = m 2 = 3and a possible exception in the case thatm 1 ∈ { 4 , 6 },m 2is even, andm 1 + m 2 ≥ 14. It has been shown previously thatOP* ( m 1 , m 2 )has a solution ifm 1 + m 2is odd, and thatOP* ( m , m )has a solution if and only ifm ≠ 3. In addition to solving many other cases ofOP*, we show that when2 ≤ m 1 + ⋯ + m k ≤ 13,OP* ( m 1 , … , m k )has a solution if and only if( m 1 , … , m k ) ∉ { ( 4 ) , ( 6 ) , ( 3 , 3 ) }.