Problem dodeljevanja frekvenc išče ustrezno dodelitev frekvenc oddajnikom v brezžičnem omrežju in obsega množico specifičnih podproblemov. Poseben primer je problem pakirnega barvanja grafov, ki izhaja iz regulacije dodeljevanja frekvenc radijskim postajam. Problem je opisan s pomočjo teorije grafov kot pakirno kromatično število $\chi_{\rho}(G)$ grafa $G$. Pakirno kromatično število grafa $G$ je najmanjše tako celo število $k$, da obstaja razbitje množice vozlišč $V(G)$ v disjunktne razrede $X_1, . . . , X_k$ s pogojem, da imajo vozlišča v $X_i$ medsebojno razdaljo večjo kot $i$. Problem določitve pakirnega kromatičnega števila je znan kot NP-težek. Članek predstavlja uporabo modela celoštevilskega linearnega programiranja ter modela problema izpolnjivosti za izračun pakirnega kromatičnega števila. Modela sta uporabljena za študij pakirnega kromatičnega števila kartezičnih produktov poti in ciklov ter razdaljnih grafov.
COBISS.SI-ID: 21043464
Naj $\rho(G)$ označuje število konveksnih ciklov enostavnega grafa $G$ z $n$ vozlišči, $m$ povezavami in z ožino $3 \leq g \leq n$. Dokazano je, da velja $\rho(G) \leq \frac{n}{g} (m-n+1)$ in da enakost velja natanko tedaj, ko je $G$ sod cikel ali Mooreov graf. Enakost velja tudi za (morebitni) Mooreov graf premera 2 in stopnje 57, zato naš rezultat predstavlja tudi novo karakterizacijo Mooreovih grafov.
COBISS.SI-ID: 17363801
Vizingova domneva iz leta 1968 trdi, da je dominantno število kartezičnega produkta dveh grafov vsaj tolikšno kot produkt njunih dominantnih števil. V tem prispevku uporabimo nov, pregleden pristop za dokaz Vizingove domneve za grafe z dominantnim številom 3; natančneje povedano, dokažemo, da za vsak graf $G$, za katerega velja $\gamma(G)=3$ in poljuben graf $H$, velja neenakost $\gamma(G\Box H)\ge 3\gamma(H)$.
COBISS.SI-ID: 17453401
b-kromatičen indeks $\varphi'(G)$ grafa $G$ je največje naravno število $k$, za katerega obstaja pravilno $k$-barvanje povezav grafa $G$, v katerem obstaja v vsakem barvnem razredu vsaj ena povezava, ki je incidenčna s kako povezavo iz vsakega drugega barvnega razreda. Določen je b-kromatičen indeks za drevesa, ki je enak naravni zgornji meji $m'(T)$ ali za ena manjši. Pri tem je $m'(T)$ povezan s številom povezav velike stopnje. Podanih je nekaj pogojev, za katere je b-kromatični indeks strogo manjši od $m'(G)$ in za katere je enak $m'(G)$. V zadnjem delu so obravnavani regularni grafi. Dokazano je, da je b-kromatični indeks kubičnega grafa 5, razen štirih izjem, ki so $K_4$, $K_{3,3}$, prizma nad $K_3$ in kocka $Q_3$.
COBISS.SI-ID: 17435225
Fowler in Pisanski sta vpeljala pojem HL-indeksa grafov, ki ima pomembno uporabo v matematični kemiji in ki nam pove, kakšna je absolutna vrednost medijanskih lastnih vrednosti grafa. V članku je dobljena natančna zgornja meja za HL-indeks poljubnih grafov z maksimalno stopnjo 3. Dokaz prinese nova orodja in rezultate o porazdelitvi lastnih vrednosti obravnavanih grafov.
COBISS.SI-ID: 17632345