Razširjanje in ojačano pronicanje v produktih grafovHedžet, Jaka (Avtor) Brešar, Boštjan (Mentor) Henning, Michael (Komentor) ojačano pronicanjeojačitveno število pronicanjarazširjanjekartezični produktdirektni produktkrepki produktmrežakubični grafdrevo.V doktorski disertaciji obravnavamo spreminjanje stanja vozlišč grafa po pravilu procesa, imenovanega $r$-ojačano pronicanje. Bolj podrobno se lotimo preučevanja tega procesa na standardnih grafovskih produktih in vpeljemo nov pojem, imenovan razširjanje, ki sestoji iz kombinacije pravil ojačanega pronicanja ter ničelne prisile oziroma $k$-prisile. Po uvodnih poglavjih je disertacija razdeljena na pet delov, znotraj katerih predstavimo rezultate na omenjeno temo. V prvem delu obravnavamo proces pronicanja na kartezičnih mrežah, ki so kartezični produkti poti. Natančneje, določimo $3$-ojačitveno število pronicanja za kartezične mreže velikosti $3 \times n$ in $5 \times n$, kjer je $n$ poljubno naravno število. Dodatno omejimo vrednost $3$-ojačitvenega števila za kartezično mrežo velikosti $4\times n$ na dve možni vrednosti. V drugem delu disertacije se usmerimo v preučevanje pronicanja na krepkih produktih grafov, in sicer za poljubno število faktorjev. Določimo vrednosti za prag $r$, pri katerih $r$-ojačitveno število produkta $k$ grafov zasede svojo trivialno spodnjo mejo, ki je enaka $r$. Nadalje postavimo dodatne pogoje za faktorje krepkega produkta, pri katerih ohranimo enako lastnost $r$-ojačitvenega števila za višji prag $r$. Posebej se lotimo tudi najmanjšega primera, ki ni zajet v teh rezultatih, to je produkt dveh faktorjev in prag $r=3$, kjer karakteriziramo tiste krepke produkte, katerih $3$-ojačitveno število je enako $3$. Raziskavo razširimo na neskončne grafe, kjer opazujemo obnašanje $r$-ojačitvenega števila na krepkih produktih dvosmernih neskončnih poti. V tretjem delu se lotimo še zadnjega izmed treh standardnih komutativnih grafovskih produktov, to je direktnega produkta grafov. Določimo nekaj zgornjih mej za $r$-ojačitveno število direktnega produkta dveh grafov in karakteriziramo grafe, ki dosežejo dve zgornji meji v primeru praga $r=2$. Določimo tudi natančne vrednosti za $r$-ojačitveno število produkta dveh poti poljubnih dolžin in med drugim okarakteriziramo tiste direktne produkte grafov, katerih $2$-ojačitveno število je enako redu enega izmed faktorjev. Četrti in zadnji del doktorske disertacije posvetimo vpeljavi in preučevanju pojma razširjanje. Posplošimo do sedaj znane rezultate iz procesov pronicanja in $k$-prisile ter zapolnimo nekatere vrzeli pri rezultatih o kartezičnih mrežah in dokažemo, da je problem razširjanja NP-težek. Z vidika razširjanja dodatno preučujemo kubične grafe brez krempljev, kjer določimo bodisi natančne vrednosti, bodisi meje za vse variante razširjevalnega števila, in drevesa, kjer predstavimo algoritem za iskanje najmanjše širitvene množice poljubnega drevesa.[J. Hedžet]20252025-05-26 10:59:42Doktorsko delo/naloga92918sl