On hypohamiltonian snarks and a theorem of Fiorini

angleški

2018

letnik 14, številka 2

Fiorinijev izrek   hipohamiltonski snarki   nepoenostavljivi snark   skalarni produkt

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

Leta 2003 so Cavicchioli in drugi zapolnili vrzeli v formulaciji in dokazu Fiorinijevega izreka iz 1983 o hipohamiltonskih snarkih. Vendar pa njihova razlčica tega izreka vsebuje za določene primere neizpolnljivi pogoj. Obravnavamo in razširimo rezultate tako Fiorinija kot tudi Cavicchiolija in drugih in predstavimo različico tega izreka, ki je splošnejša v več pogledih. Z uporabo Fiorinijevega napačnega rezultata je Steffen pokazal, da hipohamiltonski snarki obstajajo za nekatere rede ?$n \geq 10$? in celo za ?$n \geq 92$?. Konsolidiramo Steffenov dokaz, ko podamo pravilen dokaz tehnične leme o rožnih snarkih, ki je morda zanimiva tudi sama po sebi. Nato okrepimo Steffenov izrek in mu damo najmočnejšo možno obliko, ko določimo vse rede, za katere hipohamiltonski snarki obstajajo. To izboljša tudi rezultat Máčajová in Škoviere. Nazadnje potrdimo še Steffenovo domnevo o hipohamiltonskih snarkih za takšne z do 36 vozlišči.

29.05.2020