ARIS projekt N1-0431, “Dominacija v grafih: kubični grafi, produkti in igre”
(https://cris.cobiss.net/ecris/si/sl/project/23367)
Vodilni partner: Univerza v Mariboru, Fakulteta za naravoslovje in matematiko
Vodja projekta: Boštjan Brešar
Trajanje projekta: 1. 9. 2025 – 31. 8. 2028
Ostali člani projekta:
- Tanja Dravec
- Jasmina Ferme
- Jaka Hedžet
- Marko Jakovac
- Sandi Klavžar
- Andrej Taranenko
- Aleksander Vesel
Osnovni cilj projekta
Dominacija je eno najbolj intenzivno raziskovanih področij teorije grafov. Cilj projekta je osvetliti nekatere pomembne odprte probleme in domneve grafovske dominacije in prispevati nove vpoglede, ki bi lahko vodili do rešitev teh problemov. Naše delo je osredotočeno na tri teme: (i) zgornje meje dominacijskih invariant v kubičnih grafih, (ii) dominacija v produktih grafov in (iii) dominacijske igre.
Povzetek
Določitev dominacijskih števil je računsko zahteven problem, zato je pomembno dobiti ostre zgornje meje za ta števila v pomembnih razredih grafov. Še posebej zanimivo je dobiti asimptotično ostre zgornje meje za dominacijske invariante, izražene kot funkcije reda grafa. Za več dobro znanih dominacijskih invariant so bile zastavljene zahtevne domneve o njihovih zgornjih mejah v kubičnih (3-regularnih) grafih. Naš cilj je prispevati najboljše delne rezultate za nekatere od teh odprtih problemov, ki bodo potencialno vodili k njihovim končnim rešitvam. Dodaten cilj je nadgraditi obstoječe ali razviti nove metode za dokazovanje zgornjih mej za dominacijske invariante v družinah grafov, s poudarkom na regularnih grafih in grafih z določeno najmanjšo stopnjo. Glavni poudarek bo na obravnavi neodvisnostnega dominantnega števila, kjer bomo naskakovali Goddard-Henningovo domnevo, ki okrepi znameniti Reedov izrek. Obravnavali bomo tudi nekatere druge invariant dominacijskega tipa v kubičnih in splošneje regularnih grafih.
Izhodišče večine dosedanjih raziskav dominacijskih invariant v produktih grafov je znamenita Vizingova domneva o dominacijskem številu kartezičnega produkta dveh grafov, ki kljub mnogim poskusom in delnim rezultatom ostaja nerešena. Zahtevnost te domneve je vzpodbudila mnogo sorodnih vprašanj, povezanih z dominacijo v produktih grafov, ki se jih bomo lotili v okviru tega projekta. Tako bo naš cilj določiti spodnje meje za več različic dominacijskega števila, izraženega kot produkt ustreznih dominacijskih števil faktorskih grafov. Dominacijsko število je bilo najbolj raziskovano na kartezičnem produktu grafov, v okviru projekta pa bomo preučevali tudi sorodna vprašanja za druge standardne produkte grafov in pomembne inačice dominacijskega števila. Lotili se bomo tudi nekaterih pomožnih tem (npr. lastnosti kritičnih grafov za dominantno število, delno dominacijo ipd.), za katere obstajajo indici, da bi lahko pripomogle k novim najboljšim spodnjim mejam za dominacijska števila v kartezičnih produktih grafov.
V tretji temi bomo preučevali dominacijsko igro, vpeljano leta 2010, in naslovili več zanimivih odprtih problemov, povezanih z izvirno igro in njenimi različicami. Teorijo dominacijskih iger želimo nadalje razvijati s poglobitvijo obravnave najpomembnejših različic dominacijske igre ter z raziskovanjem novejših različic, kot so indicirana dominacijska igra in pristranske dominacijske igre tipa izdelovalec-lomilec. Pričakujemo, da bomo prispevali k razvoju teorije dominacijskih iger z rešitvijo nekaterih pomembnih odprtih problemov ter celovito obravnavo novih različic iger tega tipa.
