magistrsko delo
Eva Zmazek (Author), Sandi Klavžar (Mentor)

Abstract

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. 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$▫.

Keywords

magistrska dela;Hanojski graf;Hanojski stolp;anti-Ramseyevo število;mavrica;

Data

Language: Slovenian
Year of publishing:
Typology: 2.09 - Master's Thesis
Organization: UM FNM - Faculty of Natural Sciences and Mathematics
Publisher: [E. Zmazek]
UDC: 519.17(043.2)
COBISS: 24867592 Link will open in a new window
Views: 537
Downloads: 84
Average score: 0 (0 votes)
Metadata: JSON JSON-RDF JSON-LD TURTLE N-TRIPLES XML RDFA MICRODATA DC-XML DC-RDF RDF

Other data

Secondary language: English
Secondary title: Properties of the graphs of the Tower of Hanoi
Secondary abstract: 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$▫.
Secondary keywords: master theses;Hanoi graph;tower of Hanoi;anti-Ramsey number;rainbow;
Type (COBISS): Master's thesis/paper
Thesis comment: Univ. v Mariboru, Fak. za naravoslovje in matematiko, Oddelek za matematiko in računalništvo
Pages: VIII, 73 str.
ID: 11198525