Vizing's conjecture: a survey and recent resultsBrešar, Boštjan (Avtor) Dorbec, Paul (Avtor) Goddard, Wayne (Avtor) Hartnell, Bert L. (Avtor) Henning, Michael A. (Avtor) Klavžar, Sandi (Avtor) Rall, Douglas F. (Avtor) matematikateorija grafovkartezični produktdominacijaVizingova domnevamathematicsgraph theoryCaretesian productdominationVizing's conjectureVizingova domneva iz leta 1968 trdi, da je dominacijsko število kartezičnega produkta dveh grafov vsaj tako veliko, kot je produkt dominacijskih števil faktorjev. V članku naredimo pregled različnih pristopov k tej osrednji domnevi iz teorije grafovske dominacije. Ob tem dokažemo tudi nekaj novih rezultatov. Tako so na primer pokazane nove lastnosti minimalnega protiprimera, dokazana je tudi nova spodnja meja za produkte grafov brez induciranega ▫$K_{1,3}$▫ s poljubnimi grafi. Skozi celoten članek so obravnavani pripadajoči odprti problemi, vprašanja in sorodne domneve.20122015-07-10 15:23:45Delo ni kategorizirano51911UDK: 519.17OceCobissID: 25747712COBISS_ID: 16083801ISSN pri članku: 0364-9024NUK URN: URN:SI:UM:DK:NL0V9DOPsl