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
Če je $S=(a_1,a_2,\ldots)$ nepadajoče zaporedje naravnih števil, potem je $S$-pakirno barvanje grafa $G$ taka particija množice vozlišč $V(G)$ na množice $X_1,X_2, \ldots$, da je razdalja med vsakima različnima vozliščema poljubne množice $X_i$ večja kot $a_i$. Če obstaja tako število $k$, da je $V(G)=X_1\cup \cdots \cup X_k$, potem particijo imenujemo $S$-pakirno $k$-barvanje. Najmanjše tako število $k$, da $G$ premore $S$-pakirno $k$-barvanje imenujemo $S$-pakirno kromatično število grafa $G$. Če je $a_i=i$ za vsa naravna števila $i$, potem se izraza poenostavita v pakirno barvanje in pakirno kromatično število. Od vpeljave teh posplošitev kromatičnega števila v letu 2008 je bilo objavljenih preko 50 člankov na to temo. V tem članku naredimo pregled stanja na področju pakirnih barvanj in njihovih posplošitev $S$-pakirnih barvanj. Predstavimo tudi več odprtih problemov in domnev.
COBISS.SI-ID: 23220483
Število splošne lege ${\rm gp}(G)$ povezanega grafa $G$ je moč največje množice vozlišč $S$, tako da nobena tri paroma različna vozlišča iz $S$ ne ležijo na skupni najkrajši poti. Kartezični produkt $n$ kopij v obe smeri neskončne poti $P_\infty$ se imenuje $n$-dimenzionalna rešetka in označuje z $P_\infty^n$. V članku je dokazano, da za vsak $n \in {\mathbb N}$ velja ${\rm gp}({P_\infty^n}) = 2^{2^{n-1}}$. Ta rezultat je bil do sedaj znan le za $n\in \{1,2\}$ and delno za $n=3$.
COBISS.SI-ID: 32039683