Search the digital library catalog

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. \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$.
Keywords: Hanojski graf, Hanojski stolp, anti-Ramseyevo število, mavrica
Published in DKUM: 05.11.2019; Views: 493; Downloads: 80
Full text (554,90 KB)

Abstract: Geodesic covering problems form a widely researched topic in graph theory. One such problem is geodetic problem introduced by Harary et al. Here we introduce a variation of the geodetic problem and call it strong edge geodetic problem. We illustrate how this problem is evolved from social transport networks. It is shown that the strong edge geodetic problem is NP-complete. We derive lower and upper bounds for the strong edge geodetic number and demonstrate that these bounds are sharp. We produce exact solutions for trees, block graphs, silicate networks and glued binary trees without randomization.
Keywords: geodetic problem, strong edge geodetic problem, computational complexity, transport networks
Published in DKUM: 03.11.2017; Views: 670; Downloads: 342
Full text (657,86 KB)
This document has many files! More...

Abstract: V članku vpeljemo koncept zaščitenega podgrafa. Množica le-teh po definicji leži med množico konveksnih in 2-izometričnih podgrafov, hkrati pa ni primerljiva z množico izometričnimih podgrafov. Dokažemo nekatere metrične lastnosti zaščitenih podgrafov ter koncept uporabimo v dominacijski igri, v kateri dva igralca, Dominator in Zavlačevalka, izmenično izbirata vozlišča grafa, tako da vsako izbrano vozlišče poveča množico dominiranih vozlišč. Dominatorjev cilj je končati igro, tj. dominirati celoten graf, čim hitreje, medtem ko je Zavlačevalkin cilj odigrati čim več potez. Igralno dominacijsko število je število potez v igri, ko Dominator začne in oba igralca igrata optimalno. Kot glavni rezultat članka dokažemo, da igralno dominacijsko število grafa ni nikoli manjše, kot igralno dominacijsko število njegovega zaščitenega podgrafa. Predstavljenih je tudi več aplikacij tega rezultata.
Keywords: dominacijska igra, igralno dominacijsko številko, konveksni podgraf, (2-)izometrični podgraf
Published in DKUM: 10.07.2017; Views: 820; Downloads: 114
Full text (690,85 KB)
This document has many files! More...

Abstract: If ▫$f$▫ is a binary word and ▫$d$▫ a positive integer, then the generalized Fibonacci cube ▫$Q_d(f)$▫ is the graph obtained from the ▫$d$▫-cube ▫$Q_d$▫ by removing all the vertices that contain ▫$f$▫ as a factor, while the generalized Lucas cube ▫$Q_d(\stackrel{\leftharpoondown}{f})$▫ is the graph obtained from ▫$Q_d$▫ by removing all the vertices that have a circulation containing ▫$f$▫ as a factor. The Fibonacci cube ▫$\Gamma_d$▫ and the Lucas cube ▫$\Lambda_d$▫ are the graphs ▫$Q_d({11})$▫ and ▫$Q_d(\stackrel{\leftharpoondown}{11})$▫, respectively. It is proved that the connectivity and the edge-connectivity of ▫$\Gamma_d$▫ as well as of ▫$\Lambda_d$▫ are equal to ▫$\left\lfloor \frac{d+2}{3}\right\rfloor$▫. Connected generalized Lucas cubes are characterized and generalized Fibonacci cubes are proved to be 2-connected. It is asked whether the connectivity equals minimum degree also for all generalized Fibonacci/Lucas cubes. It was checked by computer that the answer is positive for all ▫$f$▫ and all ▫$d \le9$▫.
Keywords: Fibonacci cube, Lucas cube, generalized Fibonacci cube, generalized Lucas cube, connectivity, combinatorics on words
Published in DKUM: 10.07.2017; Views: 761; Downloads: 137
Full text (740,04 KB)
This document has many files! More...

Abstract: The domination game is played on an arbitrary graph ▫$G$▫ by two players, Dominator and Staller. The game is called Game 1 when Dominator starts it, and Game 2 otherwise. In this paper bluff graphs are introduced as the graphs in which every vertex is an optimal start vertex in Game 1 as well as in Game 2. It is proved that every minus graph (a graph in which Game 2 finishes faster than Game 1) is a bluff graph. A non-trivial infinite family of minus (and hence bluff) graphs is established. Minus graphs with game domination number equal to 3 are characterized. Double bluff graphs are also introduced and it is proved that Kneser graphs ▫$K(n,2)$▫, za ▫$n \ge 6$▫, are double bluff. The domination game is also studied on generalized Petersen graphs and on Hamming graphs. Several generalized Petersen graphs that are bluff graphs but not vertex-transitive are found. It is proved that Hamming graphs are not double bluff.
Keywords: domination game, game domination number, bluff graphs, minus graphs, generalized Petersen graphs, Kneser graphs, Cartesian product of graphs, Hamming graphs
Published in DKUM: 09.05.2017; Views: 791; Downloads: 386
Full text (56,60 KB)
This document has many files! More...