Vizingova domneva je najpomembnejši odprt problem v dominacijski teoriji, ki je bil zastavljen že v letu 1968. Domneva trdi, da je dominacijsko število kartezičnega produkta dveh grafov vsaj tako veliko, kot je produkt dominacijskih števil faktorjev. Pri reševanju tega problema in razvoju teorije sorodnih problemov aktivno sodelujemo tudi nekateri člani naše projektne skupine. V članku naredimo pregled različnih pristopov k tej osrednji domnevi iz teorije grafovske dominacije in 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.
COBISS.SI-ID: 16083801
V tem članku obravnavamo različne probleme, ki zadevajo kvaziprirejanja in polprirejanja v dvodelnih grafih, ki posplošujejo klasični problem določitve popolnega prirejanja v dvodelnih grafih. Dokažemo posplošitev Hallovega poročnega izreka in predstavimo algoritem, ki reši problem določitve leksikografsko minimalnega $g(v)$-kvaziprirejanja. Ugotovimo, da je najti leksikografsko minimalno kvaziprirejanje ekvivalentno minimizaciji poljubne krepko konveksne funkcije na stopnjah A-strani kvaziprirejanja in uporabimo to dejstvo za dokaz splošnejše trditve. Predstavimo tudi aplikacijo v dizajnu optimalnega brezžičnega senzorskega omrežja, ki temelji na CDMA-tehnologiji.
COBISS.SI-ID: 16191577
V članku avtorji združijo dve doslej ločeni področji v aditivni teoriji števil. Prvo gradi na posplošitvah izreka Erdös-Ginzbur-Ziv, drugo pa na fundamentalnem Kneserjevem izreku. Za njihov glavni izrek se izkaže, da ima za posledico več rezultatov, ki so bili doslej nepovezani. Čeprav ta članek predstavlja vrhunec nekega področja, pa iz njegovih rezultatov izhaja, da so možne še nekatere doslej neslutene posplošitve v smeri daljnosežne hipoteze Seymourja in Schrijverja, ki združuje algebrsko in kombinatorično plat aditivne teorije števil preko teorije matroidov.
COBISS.SI-ID: 15116377
Eno od glavnih področij projekta je obravnava različnih konveksnosti v povezavi z metrično teorijo grafov. V tem članku obravnavamo $g_3$▫-konveksnost v grafu $, ki zajema tiste množice, pri katerih je Steinerjev interval poljubne trojice njihovih vozlišč v celoti vsebovan v njih. Henning, Nielsen in Oellermann (2009) so dokazali, da graf G, v katerem so j-krogle g_3-konveksne za vsak j)0, ne vsebuje hiše niti grafov dvojčkov C_4 kot induciranih podgrafov in je vsak cikel v G dolžine vsaj 6 dobro premostljiv. V tem članku dokažemo, da velja tudi obrat tega izreka, s čimer okarakteriziramo grafe z g_3-konveksnimi kroglami.
COBISS.SI-ID: 16079193