387 KB33 KB200820252019Burgess, Andrea C.Danziger, PeterTraetta, Tommasoštevilka:1letnik:17str. 67-78ISSN:1855-3966COBISSID_HOST:18912601URN:URN:NBN:SI:doc-RKIM2139enUniverza na Primorskem, Fakulteta za matematiko, naravoslovje in informacijske tehnologijeArs mathematica contemporanea(generalized) Oberwolfach problem(posplošeni) oberwolfaški problem2-factorizations2-faktorizacijecycle systemsHamilton-Waterloo problemhamilton-waterloojski problemresolvable cycle decompositionsrešljive dekompozicije ciklovsistemi ciklovOn the generalized Oberwolfach problem|The generalized Oberwolfach problem ?$\rm{OP}_t(2w + 1; N_1, N_2, \dots , Nt; \alpha_1, \alpha_2, \dots, \alpha_t)$? asks for a factorization of ?$K_{2w + 1}$? into ?$\alpha_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 \ge 3$?) for ?$i=1, 2, \dots , t$?. Necessarily, ?$N=\mathrm{lcm}(N_1, N_2, \dots, N_t)$? is a divisor of ?$2w + 1$? and ?$w=\sum^t_{i=1} \alpha_i$?. For ?$t=1$? we have the classic Oberwolfach problem. For ?$t=2$? this is the well-studied Hamilton-Waterloo problem, whereas for ?$t \ge 3$? very little is known. In this paper, we show, among other things, that the above necessary conditions are sufficient whenever ?$2w + 1 \ge (t + 1)N$?, ?$\alpha_i > 1$? for every ?$i \in \{1, 2, \dots, t\}$?, and ?$\mathrm{gcd} (N_1, N_2, \dots, 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 graphPri 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 grafomTEXTznanstveno časopisjejournalsSlovenian National E-content AggregatorNational and University Library of SloveniaUniverza na Primorskem, Fakulteta za naravoslovje, matematiko in informacijske tehnologije