On the generalized Oberwolfach problem

angleški

2019

letnik 17, številka 1

(posplošeni) oberwolfaški problem   2-faktorizacije   hamilton-waterloojski problem   rešljive dekompozicije ciklov   sistemi ciklov

Univerza na Primorskem, Fakulteta za naravoslovje, matematiko in informacijske tehnologije
(Obvezni izvod spletne publikacije)

Pri posplošenem oberwolfaškem problemu ?$\rm{OP}_t(2w + 1; N_1, N_2, \dots , Nt; \alpha_1, \alpha_2, \dots, \alpha_t)$? iščemo faktorizacijo grafa ?$K_{2w + 1}$? na ?$\alpha_i C_{N_i}$?-faktorjev (kjer je ?$C_{N_i}$?-faktor grafa ?$K_{2w + 1}$? vpeti podgraf, katerega komponente so cikli dolžine ?$N_i \ge 3$?) za ?$i=1, 2, \dots , t$?. Potrebni pogoj za rešitev je, da je ?$N=\mathrm{lcm}(N_1, N_2, \dots, N_t)$? delitelj števila ?$2w + 1$? in da je ?$ w=\sum^t_{i=1} \alpha_i$?. Za ?$t=1$? imamo klasični oberwolfaški problem. Za ?$t=2$? je to dobro raziskani hamilton-waterloojski problem, medtem ko je za ?$t \ge 3$? znanega zelo malo. V tem članku med drugim pokažemo, da je zgornji potrebni pogoj tudi zadosten, kadarkoli je ?$2w + 1 \ge (t + 1)N$?, $?\alpha_i > 1$? za vsak ?$i \in \{1, 2, \dots, t\}$?, in ?$\mathrm{gcd} (N_1, N_2, \dots, N_t) > 1$?. Podamo tudi zadostne pogoje za rešljivost posplošenega oberwolfaškega problema nad poljubnim grafom in, še posebej, polnim ekvipartitnim grafom.

29.05.2020