A note on nowhere-zero 3-flows and Zsub3-connectivity

angleški

2016

letnik 10, številka 1

celoštevilski tok   nikjer-ničeln 3-tok   orientacija po modulu 3   povezavni rezi

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

V teoriji celoštevilskih tokov je veliko odprtih problemov, kot so Tuttejeva domneva o 3-toku, po kateri vsak 4-povezavno-povezan graph dopušča nikjer-ničeln 3-tok, domneva Jaegerja in soavtorjev, da je vsak 5-povezavnopovezan graf ?$Z_3$?-povezan, in Kocholova domneva, da vsak brezmostni graf z največ tremi 3-povezavnimi-rezi dopušča nikjer-ničelni 3-tok (ekvivalentna različica domneve o 3-toku). Thomassen je dokazal, da je vsak 8-povezavno-povezan graf ?$Z_3$?-povezan in da zato dopušča nikjer-ničeln 3-tok. Nadalje so Lovasz, Thomassen, Wu in Zhang izboljšali Thomassenov rezultat na 6-povezavno-povezane grafe. V članku dokažemo, da: (1) Vsak 4-povezavno-povezan graf z največ sedmimi 5-povezavnimi-rezi dopušča nikjer-ničelni 3-tok. (2) Vsak brezmostni graf, ki ne vsebuje nobenih 5-povezavnihrezov, vsebuje pa največ tri 3-povezavne-reze dopušča nikjerničelni 3-tok. (3) Vsak 5-povezavno-povezani graf z največ petimi 5-povezavnimi-rezi je ?$Z_3$?-povezan. Naši glavni izreki predstavljajo delne rezultate za Tuttejevo domnevo o 3-toku, za Kocholovo domnevo ter za domnevo Jaegerja in soavtorjev.

29.05.2020