472 KB69 KB200820252018Bokal, DragoLeanos, Jesúsletnik:15številka:2str. 383-406COBISSID:18551385ISSN:1855-3966URN:URN:NBN:SI:doc-B8TISBUWenUniverza na Primorskem, Fakulteta za matematiko, naravoslovje in informacijske tehnologijeArs mathematica contemporaneaizjemni primerikrižno številopodgrafi Kuratowskegatteorija grafovCharacterizing all graphs with 2-exceptional edges|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 grafovTEXTznanstveno časopisjejournalsSlovenian National E-content AggregatorNational and University Library of SloveniaUniverza na Primorskem, Fakulteta za naravoslovje, matematiko in informacijske tehnologije