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.
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11379/517004
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 2
  • ???jsp.display-item.citation.isi??? 2
social impact