Vpeljemo koncept poštenega sprejema grafa, ki je povezan z njegovim dominantnim številom. Dokažemo, da za vse grafe, ki imajo pošten sprejem velikosti njihovega dominantnega števila, velja Vizingova domneva o dominantnem številu kartezičnega produkta grafov, s čimer posplošimo dobro znan rezultat Barcalkina in Germana o razstavljivih grafih. S kombiniranjem na\v sega koncepta in rezultata Aharonija, Bergerja in Ziva dobimo alternativen dokaz izreka Aharonija in Szaba, ki pravi, da tetivni grafi zadoščajo Vizingovi domnevi.
COBISS.SI-ID: 15170393
Pakirno kromatično število \chi_\rho(G) grafa G je najmanjše število k, tako da lahko množico vozlišč grafa G razbijemo v razrede X_1,...,X_k, kjer so vozlišča iz X_i paroma na razdalji večji od i. Za kartezični produkt poti in dvodimenzionalne kvadratne mreže je dokazano, da za vsak m\ge 2 velja \chi_\rho(P_m \square {\mathbb{Z}}^2) = \infty. Nadalje je dokazano, da za vsak končen graf G velja \chi_\rho(G \square{\mathbb{Z}}) ( \infty.
COBISS.SI-ID: 15146585
Obravnavali smo (ciklične) Grayjeve kode, ki se izognejo podani množici prepovedanih povezav, ki tvorijo prirejanje. Za dano prirejanje M in dve točki u,v v Qn, n?4, naš rezultat poda potrebne in zadostne pogoje s prepovedanimi konfiguracijami za M, za obstoj Grayeve kode med u in v, ki ne vsebuje nobene povezave iz M.
COBISS.SI-ID: 15521369
Dokazano je, da lahko za vsako fiksno konstanto k vsoto razdalj med vsemi pari vozlišč abstraktnega grafa z n vozlišči in drevesno širino kvečjemu k izračunamo v času O(n log^{k-1}n). Dakazano je tudi, da lahko za vsako fiksno konstanto k raztezanje geometrijskega grafa z n vozlišči in drevesno širino kvečjemu k izračunamo v pričakovanem času O(n log^{k+1} n).
COBISS.SI-ID: 15160409
Glavni izrek članka pove, poenostavljeno rečeno, da ima vsak dovolj velik graf, katerega povezanost je linearno odvisna od parametra t, velik polni dvodelni graf K(t,k) (za poljubno velik k) kot minor. S pomočjo tega izreka avtorji naenkrat razrešijo številne odpre probleme in domneve, med katerimi se posebej izstopata Maderjeva domneva iz 70-ih let prejšnjega stoletja in Thomasonova domneva iz leta 1982.
COBISS.SI-ID: 15145049