20.500.12556/DKUM-92918 Razširjanje in ojačano pronicanje v produktih grafov Spreading and bootstrap percolation in graph products 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. In the doctoral dissertation, we study the change of states of graph vertices according to the rule of a process called $r$-bootstrap percolation. More specifically, we examine this process on standard graph products and introduce a new concept called spreading, which combines the rules of bootstrap percolation and zero-forcing or $k$-forcing. The dissertation is composed of four parts, within which we present the discovered results on the mentioned topics. In the first part, we study the percolation process on Cartesian grids, which are Cartesian products of paths. More precisely, we determine the $3$-bootstrap percolation number for Cartesian grids of size $3 \times n$ and $5 \times n$, where $n$ is an arbitrary positive integer. Additionally, we restrict the value of the $3$-bootstrap percolation number for Cartesian grids of size $4 \times n$ to two possible values. In the second part of the dissertation, we focus on studying percolation on strong products of graphs, considering an arbitrary number of factors. We determine the values for the threshold $r$ at which the $r$-bootstrap percolation number of the product of $k$ graphs attains its trivial lower bound, which is equal to $r$. Furthermore, we establish additional conditions for the factors of the strong product under which this property of the $r$-bootstrap percolation number holds for a higher threshold $r$. We also examine the smallest case not covered by these results, namely the product of two factors with threshold $r=3$, where we characterize the strong products for which their $3$-percolation number is equal to $3$. Our research extends to infinite graphs, where we observe the behavior of the $r$-bootstrap percolation number on strong products of two-directional infinite paths. In the third part, we address the last of the three fundamental commutative graph products, namely the direct product of graphs. We determine some upper bounds for the $r$-bootstrap percolation number of the strong product of two graphs and characterize graphs that achieve two upper bounds in the case of threshold $r=2$. Among others we characterize the direct products for which the $2$-percolation number is equal to the order of one of the factors. We also determine exact values for the $r$-bootstrap percolation number of the product of two paths of arbitrary lengths. The fourth and final part of the doctoral dissertation is dedicated to introducing and studying the concept of spreading. We generalize the previously known results from percolation processes and $k$-forcing, fill in some gaps in the results on Cartesian grids, and prove that the spreading problem is NP-hard. From the perspective of spreading we further examine claw-free cubic graphs, where we determine either exact values or bounds for all variants of the spreading number. Furthermore, we present an algorithm for finding the smallest spreading set of an arbitrary tree. ojačano pronicanje ojačitveno število pronicanja razširjanje kartezični produkt direktni produkt krepki produkt mreža kubični graf drevo. bootstrap percolation bootstrap percolation number spreading cartesian product direct product strong product grid cubic graph tree. true true false [J. Hedžet] Slovenski jezik Angleški jezik Doktorsko delo/naloga 2025-05-26 10:59:42 2025-10-06 13:57:55 2025-10-14 09:28:48 0000-00-00 00:00:00 2025 0 Maribor 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 519.17(043.3) 251921667 DOK_Hedzet_Jaka_2025.pdf DOK_Hedzet_Jaka_2025.pdf 1 6EF5103AF88D0254BA08725F6ECB9688 31df058e2d3014bb73337455c93273bb8a7c6adf5d0aa6f4f84936891290229f 8938fe91-3a11-11f0-80b9-00155d000105 https://dk.um.si/Dokument.php?lang=slv&id=191269 Fakulteta za naravoslovje in matematiko 0 0 0