The generalized Oberwolfach problem OP_t(2w + 1; N_1, N_2, …, N_t; α_1, α_2, …, α_t) asks for a factorization of K_{2w + 1} into α_i C_{N_i}-factors (where a C_{N_i}-factor of K_{2w + 1} is a spanning subgraph whose components are cycles of length N_i ≥ 3) for i = 1, 2, …, t. Necessarily, N = lcm(N_1, N_2, …, N_t) is a divisor of 2w + 1 and w = Σ_{i=1}^t α_i. For t = 1 we have the classic Oberwolfach problem. For t = 2 this is the well-studied Hamilton-Waterloo problem, whereas for t ≥ 3 very little is known. In this paper, we show, among other things, that the above necessary conditions are sufficient whenever 2w + 1 ≥ (t + 1)N, α_i > 1 for every i ∈ {1, 2, …, t}, and gcd (N_1, N_2, …, N_t) > 1. We also provide sufficient conditions for the solvability of the generalized Oberwolfach problem over an arbitrary graph and, in particular, the complete equipartite graph.
On the generalized Oberwolfach problem
Traetta, Tommaso
2019-01-01
Abstract
The generalized Oberwolfach problem OP_t(2w + 1; N_1, N_2, …, N_t; α_1, α_2, …, α_t) asks for a factorization of K_{2w + 1} into α_i C_{N_i}-factors (where a C_{N_i}-factor of K_{2w + 1} is a spanning subgraph whose components are cycles of length N_i ≥ 3) for i = 1, 2, …, t. Necessarily, N = lcm(N_1, N_2, …, N_t) is a divisor of 2w + 1 and w = Σ_{i=1}^t α_i. For t = 1 we have the classic Oberwolfach problem. For t = 2 this is the well-studied Hamilton-Waterloo problem, whereas for t ≥ 3 very little is known. In this paper, we show, among other things, that the above necessary conditions are sufficient whenever 2w + 1 ≥ (t + 1)N, α_i > 1 for every i ∈ {1, 2, …, t}, and gcd (N_1, N_2, …, N_t) > 1. We also provide sufficient conditions for the solvability of the generalized Oberwolfach problem over an arbitrary graph and, in particular, the complete equipartite graph.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.