Teorija grafova je matematička disciplina koja pronalazi primjenu u vrlo različitim područjima, kao što su fizika, lingvistika, sociologija, biologija, antropologija, računarstvo, komunikacije, itd. Grafovi su jedan od najčešće korištenih modela za prikaz prirodnih i ljudski stvorenih struktura, a također i za prikaz interakcija između različitih objekata i/ili kategorija. Oni su također prirodni modeli za široku klasu novih materijala poznatih kao nanostrukture. Ono što nanostrukture i s njima usko povezane fulerene čini toliko interesantnima za modernu znanost su njihove potencijalne primjene koje uključuju, ali se ne ograničavaju na, skladištenje vodika, supravodljive materijale i nanomedicinu. Jedna od glavnih prednosti pristupa temeljenog na teoriji grafova je da se razni grafovni invarijanti (poznati i kao molekularni deskriptori) mogu ispitati na korelacije s nekim fizikalno-kemijskim svojstvima i/ili farmakološkom i biološkom aktivnošću molekula. Ti grafovni invarijanti se računaju iz topološke informacije sadržane u strukturi molekule, koja obuhvaća položaj i, ponekad, tip atoma definiranih u odnosu na veze koje ih povezuju. Među najpoznatijim i najistraženijim invarijantima su oni temeljeni na stupnjevima i udaljenostima u molekularnim grafovima. Ovdje predlažemo razmatranje nekoliko invarijanti koji se javljaju u kontekstu sparivanja. Mnogi problemi u prirodnim, tehničkim i društvenim znanostima mogu se uspješno formulirati u terminima sparivanja u grafovima. Danas je teorija sparivanja dobro razvijena grana teorije grafova, koja proučava i strukturne i enumerativne aspekte sparivanja. Njezin razvoj snažno su stimulirale primjene u kemiji i znanosti o materijalima, posebno proučavanje perfektnih sparivanja u benzenoidnim grafovima. Dodatni poticaj došao je s otkrićem fulerena, arhetipskih nula-dimenzionalnih nanostruktura, ponovno se uglavnom baveći perfektnim sparivanjima, ali uključujući i neke strukturne rezultate. U oba područja naš zajednički istraživački timovi su akumulirali značajnu ekspertizu i objavili nekoliko vrlo zapaženih znanstvenih radova. Sparivanje M u grafu G je skup bridova grafa G takav da nikoja dva brida iz M ne dijele vrh. Kardinalnost skupa M nazivamo veličinom sparivanja. Kako su sparivanja malih veličina trivijalna, uglavnom ćemo se zanimati za sparivanja koja su, u određenom smislu, "velika". Najčešće nas interesiraju sparivanja koja su što veća moguća. Sparivanje M je maksimalno (maximum) ako ne postoji sparivanje u G s više bridova od M. Ako je svaki vrh grafa G incidentan s nekim bridom iz M, sparivanje M nazivamo perfektnim. Perfektna sparivanja su očito i maksimalna (maximum) sparivanja. Postoji, međutim, alternativan način kvantificiranja ideje "velikih" sparivanja. Sparivanje M u G je maksimalno (maximal) ako niti jedno drugo sparivanje u G ne sadrži M kao svoj pravi podskup. Očito je da je svako maksimalno (maximum) sparivanje istovremeno i maksimalno (maximal), ali obrat općenito nije istinit. Maksimalna (maximal) sparivanja su znatno manje istraživana od svojih maksimalnih (maximum) parnjaka. To vrijedi i za njihove strukturne i za njihove enumerativne aspekte. Dok postoji obimna literatura o perfektnim i maksimalnim (maximum) sparivanjima, rezultati o maksimalnim (maximal) sparivanjima su rijetki i raspršeni po literaturi. Među njima su i recentni radovi čiji su autori članovi našeg zajedničkog istraživačkog tima, o brojevima saturacije benzenoidnih grafova i fulerena. Maksimalna (maximal) sparivanja mogu služiti kao modeli nekoliko fizikalnih i tehničkih problema, kao što je blok-alokacija sekvencijalnog resursa ili adsorpcija dimera na strukturiranom supstratu ili molekuli. Kada je taj proces slučajan, jasno je da supstrat može postati zasićen s brojem dimera koji je znatno manji od teorijskog maksimuma. Kardinalnost bilo kojeg najmanjeg maksimalnog (maximal) sparivanja u G je broj saturacije grafa G, označen s s(G). Broj saturacije daje informaciju o najgorem mogućem slučaju začepljenja; on je mjera koliko neefikasan proces adsorpcije može biti. Međutim, da bismo u potpunosti procijenili njegovu efikasnost, potrebno je znati i koliko je vjerojatno da će supstrat biti zasićen određenim brojem dimera. Da bismo odgovorili na to pitanje, moramo proučiti enumerativne aspekte problema. Glavni cilj predloženog projekta je proširiti korpus znanja o enumerativnim aspektima maksimalnih (maximal) sparivanja i primijeniti rezultate na nula- i jednodimenzionalne nanostrukture. Konkretno, planiramo izračunati efikasnost adsorpcije dimera za nekoliko tipova jednodimenzionalnih supstrata enumeracijom maksimalnih (maximal) sparivanja različitih kardinalnosti u odgovarajućim grafovima, počevši od struktura niske povezanosti i istražujući kako efikasnost ovisi o strukturnim svojstvima njihovih osnovnih građevnih blokova. U nekim slučajevima očekujemo da ćemo biti u mogućnosti dobiti eksplicitne formule, dok u drugim slučajevima planiramo uspostaviti rekurzije za enumerativne nizove i zatim koristiti njihove uni- i bivarijatne funkcije izvodnice za određivanje njihovog asimptotskog ponašanja. Metode i tehnike razvijene u tijeku projekta zatim će se primijeniti za modeliranje adsorpcije općenitijih molekula na supstratima nanostruktura. Važan aspekt ovog projekta je usavršavanje doktorskih studenata. Oni će sudjelovati u unapređenju najsuvremenijih teorijskih metoda za primjenu u modeliranju kompleksnih sustava. Radeći u brzo napredujućem znanstvenom području, oni će postati vještiji u temeljnim tehnikama, kao i steći direktno iskustvo u planiranju i izvođenju dugoročnih projekata. I u Hrvatskoj i u Sloveniji te vještine su vrijedne i tražene, kako unutar, tako i izvan akademske domene.