20.500.12556/DKUM-74115 Lastnosti grafov Hanojskega stolpa Properties of the graphs of the Tower of Hanoi Hanojski grafi $H_p^n$, $n \geq 1$, $p \geq 3$, so modeli predstavitve problema Hanojskega stolpa z $n$ diski in $p$ nosilci. Njihova rekurzivna konstrukcija vodi do izpeljave nekaterih lastnosti. Kromatično število $\chi(H_p^n)$ Hanojskega grafa $H_p^n$ je na primer enako številu nosilcev $p$ prirejenega problema Hanojskega stolpa, kromatični indeks $\chi'(H_p^n)$ tega Hanojskega grafa pa je enak njegovi maksimalni stopnji vozlišč $\Delta(H_p^n)$. Vsi Hanojski grafi so Hamiltonovi, $(p-1)$-povezani, nekateri med njimi so tudi ravninski. \end{sloppypar} \begin{sloppypar} Barvanje povezav $c: E(G) \to [k]$ je mavrica, če za poljubni različni povezavi $e,f \in E(G)$ velja $c(e) \not= c(f)$. Anti-Ramseyevo število na paru grafov $G$ in $H$ je najmanjše tako število $n$, za katerega pri vsakem barvanju $c$ povezav grafa $G$ z natanko $n$ barvami, obstaja $H$-podgraf grafa $G$, za katerega je zožitev $c|H$ mavrica. V magistrski nalogi si ogledamo anti-Ramseyeva števila $\ar(H_p^n,H_q^m)$, $p,q \geq 3$, $n,m \geq 1$, na paru Hanojskih grafov, kjer je $m=n=1$ in $q=3$, in na paru Hanojskih grafov, kjer je $p=q$. Za anti-Ramseyevo število $\ar(H_p^n,H_3^1)$, $p \geq 3$, $n \geq 1$, izpeljemo rekurzivno zvezo. Pokažemo tudi, da je anti-Ramseyevo število $\ar(H_4^2,H_3^2)$ omejeno navzdol s $30$ ter navzgor s $34$. For integers $n \geq 1$ and $p \geq 3$ we define Hanoi graph $H_p^n$ as a graph model of Tower of Hanoi with $n$ discs and $p$ pegs. Because of their recursive construction, there are some nice properties of Hanoi graphs. For example, the chromatic number $\chi(H_p^n)$ of Hanoi graph $H_p^n$ is equal to the number of pegs $p$ and the chromatic index $\chi'(H_p^n)$ of the same Hanoi graph is equal to its maximum degree of a vertex, $\Delta(H_p^n)$. Each Hanoi graph $H_p^n$ is Hamiltonian and $(p-1)$-connected, and some of them are also planar. Edge coloring $c: E(G) \to [k]$ of graph $G$ is a rainbow if all of its edges are colored with different colors. Anti-Ramsey number for a pair of graphs $G$ and $H$ is the lowest number $n$ such that for every edge coloring $c$ of graph $G$ with exactly $n$ colors there exists such $H$-subgraph of graph $G$ that the coloring $c$ on it is a rainbow. In the thesis, we present the exact value of anti-Ramsey numbers $\ar(H_p^n,H_q^m)$, $p,q \geq 3$, $n,m \geq 1$, for pairs of Hanoi graph where $n=m=1$, $q=3$ and also for pairs of Hanoi graphs where $p=q$. For anti-Ramsey number $\ar(H_p^n,H_3^1)$, $p \geq 3$, $n \geq 1$ we give the recursive formula. We also show that the exact value of the anti-Ramsey number $\ar(H_4^2,H_3^2)$ is bounded with $30$ and $34$. Hanojski graf Hanojski stolp anti-Ramseyevo število mavrica Hanoi graph Tower of Hanoi anti-Ramsey number rainbow true true false [E. Zmazek] Slovenski jezik Angleški jezik Magistrsko delo/naloga 2019-08-07 10:52:27 2019-11-05 13:00:00 2022-08-09 08:15:00 2019-12-10 07:59:42 2019 0 Maribor 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 519.17(043.2) 24867592 URN:SI:UM:DK:WB8OWLPT MAG_Zmazek_Eva_2019.pdf MAG_Zmazek_Eva_2019.pdf 1 F41C06D194475BCD4D08ED876C4B1D47 4dcb006ade3e66828ab8e0eb4ea4cee94133c3de1677a60d57be85fa2ce3ede8 cf59a821-7c10-11eb-bb7a-00155d0001ca 20.500.12556/dkum/cc42130b-e693-415f-962c-388008f83675 https://dk.um.si/Dokument.php?lang=slv&id=135630 Fakulteta za naravoslovje in matematiko 0 0 0