Število vozliščnega pokritja, ki je ena najbolj osnovnih invariant grafov, lahko razumemo kot najmanjše število vozlišč, ki zadenejo vsak podgraf $K_2$ v grafu $G$. V tem članku obravnavamo dva naslednja najmanjša primera povezanih grafov, ki sta pot $P_3$ in cikel $C_3$; problem je minimizirati množico vozlišč, ki zadenejo vsak podgraf $H$ grafa $G$, kjer je $H$ eden od obeh grafov. Osredotočimo se na računske vidike teh dveh variacij števila vozliščnega pokritja. Dokažemo, da sta oba problema NP-polna celo v razredu grafov, ki nimajo induciranih ciklov dolžine $t$, kjer je $t\in\{4,\ldots, 8\}$ (v primeru grafa $P_3$ je problem NP-poln celo v manjši družini grafov, kjer so prepovedani tudi trikotniki). Na pozitivni strani pa dokažemo komplementaren rezultat, ki pravi, da v grafih, ki nimajo induciranih $P_4$ (takim grafov pravimo tudi kografi) oba problema postaneta linearna. Še več, obravnavamo tudi posplošitev kografov -- $P_4$-urejene grafe, za katere predstavimo učinkovit algoritem za oba problema.
COBISS.SI-ID: 18568025
$2$-dominantno število $\gamma_2(G)$ grafa $G$ je moč najmanjše množice $S\subseteq V(G)$, tako da je vsako vozlišče iz $V(G)\setminus S$ sosedno z vsaj dvema vozliščema iz $S$. Število uničenja $a(G)$ grafa $G$ je največje naravno število $k$, tako da je vsota prvih $k$ členov nepadajočega zaporedja stopenj grafa $G$ kvečjemu število njegovih povezav. Postavljena je bila domneva, da neenakost $\gamma_2(G) \leq a(G) +1$ velja za vsaj povezan graf $G$. Domneva je bila so sedaj med drugim potrjena za grafe z minimalno stopnjo $3$, za drevesa in za bločne grafe. V tem članku ovržemo domnevo tako, da dokažemo, da je lahko $2$-dominantno število poljubno večje od števila uničenja. Na pozitivni strani pa dokažemo, da domnevana meja velja za velik podrazred dvodelnih, povezanih kaktusov, s čimer posplošimo rezultat Jakovca iz [Discrete Appl. Math. 260 (2019) 178-187].
COBISS.SI-ID: 18966105
Dominacijska igra (Brešar in sod. v SIAM J Discrete Math 24:979-991, 2010) in celotna dominacijska igra (Henning in sod. v Graphs Comb 31:1453-1462. 2015) sta dobro znani igri na grafih za dva igralca - Dominatorja in Zavlačevalko. V tem članku vpeljemo tri nove različice dominacijske igre, in sicer Z-dominacijsko igro, L-dominacijsko igro in LL-dominacijsko igro. Za vsako izmed novih iger dokažemo princip nadaljevanja, ki nam med drugim pove, da se rezultata igre (pripadajaoči grafovski invarianti) v primerih, ko Dominator začne oziroma, ko začne Zavlačevalka, razlikujeta za največ ena. V članku vzpostavimo hierarhijo med petimi dominacijskimi igrami. Za vsako izmed novih treh iger določimo spodnjo in zgornjo mejo v odvisnosti od dominacijske ali celotne dominacijske igre ter reda grafa. Izračunali smo vrednosti novih treh invariant na poteh v odvisnosti od števila vozlišč do majhne konstante natančno. Na koncu smo našteli še nekaj odprtih problemo ter postavili domnevo, ki pravi, da L-igralno dominacijsko število ni nikoli večje kot 6/7 reda grafa.
COBISS.SI-ID: 18819673