Characterizing all graphs with 2-exceptional edges

angleški

2018

letnik 15, številka 2

izjemni primeri   križno število   podgrafi Kuratowskegat   teorija grafov

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

Dirac in Shuster sta leta 1954 predstavila enostaven dokaz izreka Kuratowskega, ko sta pokazala, da poljubna 1-križno-kritična povezava grafa ?$G$? pripada neki subdiviziji Kuratowskega grafa ?$G$?. Leta 1983 je Širáň razširil ta rezultat na poljubno tako 2-križnokritično povezavo ?$e$? s krajiščema ?$b$? in ?$c$? v grafu ?$G$? s križnim številom najmanj dve, da nobena dva bloka grafa ?$G-b-c$? ne vsebujeta vseh njegovih vozlišč. Povezavo ?$f$? grafa ?$G$? je imenoval ?$k$?-izjemna, če je ?$f$? ?$k$?-križno-kritična in ne pripada nobenemu podgrafu Kuratowskega grafa ?$G$?. Nato je pokazal, da enostavni 3-povezani grafi s ?$k$?-izjemnimi povezavami obstajajo za poljuben ?$k \ge 6$? in da obstajajo celo za poljubno velike razlike ?${\rm cr}(G) - {\rm cr}(G - f)$?. Leta 1991 je Kochol konstruiral takšne primere za poljubne ?$k \ge 4$? in pripomnil, da Širáňov rezultat velja za poljuben enostaven graf. V pričujočem članku raziščemo primer, ko dva bloka vsebujeta vsa vozlišča grafa ?$G-b-c$?, in pokažemo, da grafi s ?$k$?-izjemnimi povezavami obstajajo za poljuben ?$k \ge 2$?, vendar niso nujno enostavni. Potrdimo, da ne obstajajo nobeni takšni enostavni grafi z 2-izjemnimi povezavami, in to z uporabo tehnik iz nedavne karakterizacije 2-križno-kritičnih grafov. Eksplicitno opišemo množico vseh grafov z 2-izjemnimi povezavami in opazimo, da vsi vsebujejo vzporedne povezave. V tem kontekstu je mogoče ta članek brati kot preludij h karakterizaciji 2-križno-kritičnih grafov.

29.05.2020