20.500.12556/RUL-172982 Gorenje grafa delo diplomskega seminarja Graph burning Preučujemo proces gorenja na povezanih neusmerjenih grafih. V procesu zagorijo viri gorenja in sosednja vozlišča že zgorelih vozlišč. Zanima nas, v koliko korakih bo zagorel cel graf in to količino definiramo kot število gorenja. Izbrani viri v procesu gorenja tvorijo zaporedje gorenja. Število gorenja poiščemo za enostavne družine grafov, kot so poti, polni grafi in kolesa. Uvedemo karakterizaciji gorenja s soseščinami ter $k$-dobro razdelitvijo na drevesa s korenom ter s tem pridemo do izreka o redukciji na drevesa, ki nam omogoča prevedbo problema gorenja za splošne grafe na gorenje dreves. S pomočjo tega izreka izračunamo še število gorenja za cikle in grafe s hamiltonovo potjo. Definiramo dobro gorljivost, ki je lastnost grafov na $n$ vozliščih, ki imajo število gorenja manjše od $\lceil\sqrt{n}\rceil$. Ogledamo si nekaj dokazanih mej za domnevo o številu gorenja, ki pravi, da so vsi povezani grafi dobro gorljivi. Domneva je dokazana za nekaj družin grafov. V delu jo dokažemo za gosenice in pajke. We study the burning process on connected undirected graphs. During the process the sources burn, and the neighbors of already burned vertices burn. We are interested in the number of steps required for the entire graph to burn, a concept we define as the burning number. The chosen sources in the burning process form a burning sequence. We determine the burning number for simple graph classes such as paths, complete graphs, and wheels. We introduce two characterizations of burning: one using neighborhoods, and another using $k$-good rooted tree partitions. This leads to a tree reduction theorem, which allows us to translate the burning problem for general graphs to the burning problem for trees. Using this theorem, we compute the burning number for cycles and graphs containing a Hamiltonian path. We define well-burnable graphs, which are graphs whose burning number is less than $\lceil\sqrt{n}\rceil$. We examine several proven bounds for the burning number conjecture, which states that all connected graphs are well-burnable. The conjecture has been proven for some classes of graphs. We prove it for caterpillars and spiders. gorenje grafa število gorenja zaporedje gorenja izrek o redukciji na drevesa dobro gorljivi grafi domneva o številu gorenja drevesa graph burning burning number burning sequence tree reduction theorem well-burnable graphs burning number conjecture trees true false false Slovenski jezik Angleški jezik Delo diplomskega seminarja/zaključno seminarsko delo/naloga 2025-09-12 08:15:11 2025-09-12 08:15:13 2025-10-29 03:50:40 0000-00-00 00:00:00 2025 0 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 519.17 153203 248713219 18923.pdf 18923.pdf 1 166DFF56286F9C16317DEC3D1C8C70C6 0d5bcd85946d767935e08469a14c91d0ce7858c0ef7ca1aa80b0107bbeee2089 ae22b05a-8f9f-11f0-9328-0050569b8976 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=217134 Fakulteta za matematiko in fiziko 0 0 0