Vpeljemo in obravnavamo bukolične kompleksne, skupno posplošitev sistoličnih in CAT(0) kubnih kompleksov. Definirani so kot enostavno povezani kompleksi prizem, ki zadoščajo določenim lokalnim kombinatornim pogojem. Raziskujemo različne pristope k bukoličnim kompleksom: gledamo jih iz vidika teorije grafov in topološkega vidika kot tudi iz perspektive geometrijske teorije grup. Tako med drugim okarakteriziramo bukolične komplekse preko nekih lastnosti njihovih 2-skeletov in 1-skeletov (ki jim pravimo bukolični grafi), s čimer posplošimo več prej znanih rezultatov. Prav tako dokažemo, da so lokalno končni bukolični kompleksi kontraktibilni in da zadoščajo nekim lastnostim tipa nepozitivnih ukrivljenosti.
COBISS.SI-ID: 16633177
Vizingova domneva iz leta 1968 trdi, da je dominacijsko število kartezičnega produkta dveh grafov vsaj tako veliko, kot je produkt dominacijskih števil faktorjev. V članku naredimo pregled različnih pristopov k tej osrednji domnevi iz teorije grafovske dominacije. 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
Knjiga je nastala na osnovi knjige Product Graphs, ki je leta 2000 izšla pri WileyInterscience. Slednja je postala klasično delo o produktih grafov in predstavlja enega najbolj citiranih del slovenske matematike. V bazi MathSciNet ima že preko 250 citatov. Nova knjiga je bistveno obsežnejša (518 str. proti 358 str.) in je napisana povsem na novo ter ima povsem novo strukturo. Knjiga Priročnik o produktih grafov obravnava dihotomijo med strukturo produktov grafov in njihovimi podgrafi. Poudarja tudi načrtovanje učinkovitih algoritmov, ki prepoznavajo produkte in njihove podgrafe ter raziskuje povezave med grafovskimi parametri produktov in njihovih faktorjev. Občutno razširjena in popravljena knjiga prinaša popolne dokaze mnogih pomembnih rezultatov in tudi najnovejše rezultate in domneve. Rezultati in algoritmi, ki so novi v tej knjigi obsegajo (1) Izreke o krajšanju, (2) kvadratični prepoznavni algoritem za delne kocke, (3) rezultate o krepki izometrični dimenziji, (4) izračun Wienerjevega indeksa preko kanonične izometrične vložitve, (5) rezultate o povezanosti, (6) deljeno inačico Hedetniemijeve domneve, (7) rezultate o neodvisnostnem številu kartezičnih potenc po vozliščih tranzitivnih grafov, (8) dokaz Vizingove domneve za tetivne grafe, (9) rezultate o minimalnih bazah ciklov in (10) številne izbrane rezultate, kot na primer rezultate o polnih minorjih in nikjer ničelnih pretokih.
COBISS.SI-ID: 15916121
V delu je dokazano, da je mogoče povezave vsakega grafa omejenega roda razbiti na vnaprej predpisano število delov (k), tako da ima kontrakcija kateregakoli od teh delov omejeno drevesno širino, kjer je meja odvisna le od števila k. Podoben, a precej enostavnejši rezultat, je znan za operacijo odstranjevanja povezav namesto kontrakcije (Baker 1994, Eppstein 2000 in drugi). Dobljeno dekompozicijo uporabimo za razvoj zelo splošnih (meta)algoritmov. Med drugim dobimo polinomske aproksimacijske sheme (PTAS) za poljubne probleme, ki so monotoni za kontrakcijo povezav. Vsi taki problemi, ki izpolnjujejo še nekaj dodatnih pogojev, imajo PTAS za vse grafe omejenega roda. Tako dobimo na primer PTAS za uteženo obliko problema potujočega trgovca in za minimalni uteženi c-povezavno-povezani podmultigraf v grafih omejenega roda, kar hkrati posploši večje število znanih algoritmov.
COBISS.SI-ID: 15802457
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^{k1}n). Dokazano 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