Search

Domination game [SIAM J.\ Discrete Math.\ 24 (2010) 979--991] and total domination game [Graphs Combin.\ 31 (2015) 1453--1462] are by now well established games played on graphs by two players, named Dominator and Staller. In this paper, Z-domination game, L-domination game, and LL-domination game are introduced as natural companions of the standard domination games. Versions of the Continuation Principle are proved for the new games. It is proved that in each of these games the outcome of the game, which is a corresponding graph invariant, differs by at most one depending whether Dominator or Staller starts the game. The hierarchy of the five domination games is established. The invariants are also bounded with respect to the (total) domination number and to the order of a graph. Values of the three new invariants are determined for paths up to a small constant independent from the length of a path. Several open problems and a conjecture are listed. The latter asserts that the L-domination game number is not greater than $6/7$ of the order of a graph., 21 pages

Mostovni grafi so zelo dobro raziskana družina grafov. Pojavljajo se na različnih področjih, ne samo diskretne matematike, na primer v geometrični teoriji grup. V disertaciji se ukvarjamo z različnimi problemi, povezanimi z mostovnimi grafi in njihovimi posplošitvami. Pokažemo, do so ti grafi uporabni tudi zunaj same teorije grafov, saj jih povežemo s teorijo kompleksov. Med drugim se ukvarjamo s povezavo teh grafov in določenih tipov konveksnosti v grafih in z uporabo mostovnih grafov v grafih, prirejenih delno urejenim množicam. Disertacija je sestavljena iz treh delov, pri čemer v vsakem delu prikažemo uporabnost mostovnih grafov na izbranem področju. V prvem delu vpeljemo in proučujemo bukolične komplekse, skupno posplošitev sistoličnih in CAT(0) kubičnih kompleksov. Bukolične komplekse proučujemo z vidika teorije grafov, topološkega vidika in iz perspektive geometrijske teorije grup. Okarakteriziramo jih preko določenih lastnosti njihovih 2-skeletov in 1-skeletov (ki jim pravimo bukolični grafi), s čimer posplošimo več že znanih rezultatov. Prav tako dokažemo, da so bukolični kompleksi skrčljivi in da zadoščajo nekim lastnostim tipa nepozitivnih ukrivljenosti. V drugem delu posplošene mostovne grafe obravnavamo vzporedno s 3-Steinerjevo konveksnostjo. In sicer dokažemo, da so grafi $G$, v katerih so j-krogle g_3-konveksne za vsak j ≥ 1, natanko grafi, ki ne vsebujejo hiše niti grafov K_{2,3} in W_4^- kot induciranih podgrafov, in je vsak cikel v G, dolžine vsaj šest, dobro premostljiv. Okarakteriziramo torej grafe z g_3-konveksnimi kroglami. V tretjem delu disertacije usmerimo pozornost na grafe pokritij-neprimerljivosti delno urejenih množic (C-I grafe) in iščemo njihovo povezavo z mostovnimi grafi. Pokažemo, da v razredu C-I grafov sovpada kar nekaj različnih grafovskih družin. In sicer, v razredu C-I grafov ni razlike med mostovnimi grafi, tetivnimi grafi in grafi intervalov. Ker je problem prepoznavanja grafov pokritij-neprimerljivosti v splošnem NP-poln, se osredotočimo na določene razrede mostovnih grafov. Okarakteriziramo tiste delno urejene množice, ki imajo za graf pokritij-neprimerljivosti bločni graf oziroma razcepljeni graf. Med drugim okarakteriziramo grafe pokritij-neprimerljivosti tako med bločnimi oziroma razcepljenimi grafi kot med tetivnimi kografi. Slednje karakterizacije dajo tudi linearen algoritem za prepoznavanje bločnih oziroma razcepljenih grafov, oziroma tetivnih kografov, ki so grafi pokritij-neprimerljivosti. Bridged graphs are one of the very well investigated graf classes. They do not appear just in discrete mathematics but also in geometric group theory. In this dissertation thesis, different problems connected with bridged graphs and their generalizations are presented. They are used in the study of certain complexes, thus being applicable also outside graph theory. In particular, we present the relation between bridged graphs and some types of convexities in graphs and also the relation of these class of graphs with graphs obtained from posets. The dissertation is composed from three parts where in each part the use of bridged graphs on a chosen area is presented. In the first part we introduce and investigate bucolic complexes, a common generalization of systolic complexes and of CAT(0) cubical complexes. We study bucolic complexes from graph-theoretic and topological perspective, as well as from the point of view of geometric group theory. In particular, we characterize bucolic complexes by some properties of their 2-skeleta and 1-skeleta (that we call bucolic graphs), by which several known results are generalized. We also show that bucolic complexes are contractible, and satisfy some nonpositive-curvature-like properties. In the second part we investigate generalized bridged graphs parallel with 3-Steiner convexity. We prove that the graphs with g_3-convex j-balls for every j ≥ 1, are exactly the graphs without house, K_{2,3} and W_4^- as induced subgraphs in which all cycles of length at least six are well-bridged. Thus we characterize graphs with g_3-convex balls. In the last part of the thesis we focus on cover-incomparability graphs of posets (C-I graphs), studying the connection of these graphs with bridged graphs. We show that in the class of C-I graphs some different graph classes coincide. In particular, in the class of C-I graphs there is no difference among the bridged graphs, the chordal graphs and the interval graphs. Since the problem of recognizing cover-incomparability graphs of posets was shown to be NP-complete in general, we concentrate on (classes of) bridged graphs. We characterize the posets whose cover-incomparability graph is a block graph, and a split graph, respectively, and also characterize the cover-incomparability graphs among block graphs, split graphs and chordal cographs, respectively. The latter characterizations yield polynomial algorithms for recognition of block graphs, split graphs and chordal cographs, respectively, that are cover-incomparability graphs.

Prvi del diplomskega dela govori o predstavitvah delnih urejenosti z družinami množic, kot so družina konveksnih poligonov, družina pravilnih n-kotnikov, družina krogov ipd. Lastnost, ki nam pomaga pri raziskovanju predstavitev delnih urejenosti, je prekrižno število. Ker zlahka preverimo, da lahko poljubno končno delno urejeno množico predstavimo z družino množic in z družino konveksnih poligonov, je glavni cilj prvega dela preveriti, kakšno je prekrižno število dlenih urejenosti, ki jih lahko predstavimo z družino krogov oziroma z družino pravilnih n-kotnikov. V drugem delu diplomskega dela najprej definiramo podatkovno hierarhijo in dokažemo, da vsaka podatkovna hierarhija predstavlja delno urejenost. Glavni rezultat drugega dela je dokaz, da lahko vsako delno urejeno množico predstavimo kot podatkovno hierarhijo. Pri tem je najpomembnejša ugotovitev, da lahko vsako delno urejeno množico predstavimo z relacijo deljivosti na neki podmnožici naravnih števil in da lahko relacijo deljivosti predstavimo kot podatkovno hierarhijo. V zaključku diplomskega dela pa so vpeljane posebne vrste podatkovnih hierarhij, ki odpirajo možnosti za nadaljne raziskovanje. The first part of the thesis studies representations of partial orders using family of sets like convex polygons, regular n-gons, and circles. The feature that we use in this investigation is the crossing number. Because it is easy to check that every final poset has set representation and representation using convex polygons, our main goal is to check the crossing number of posets that we can represent with a family of circles or with family of regular n-gons. In the second part of the thesis, we first define data hierarchy, and prove that each data hierarchy presents a partial order. The main result of the second part is that each finite partial order can be represented as a data hierarchy. This is established using the fact that each finite poset can be represented by a relation of divisibility on a certain subset of natural numbers and that the relation of divisibility can be represented as a data hierarchy. In the conclusion, we present some special types of data hierarchies, which give several possibilities of further research.

V magistrskem delu je predstavljenih več učencem zanimivih matemativ cnih ugank. Najprej obravnavamo različne matematične uganke skozi zgodovino vse od magiv cnih kvadratov do ugank novejv sega v casa kot je rubikova kocka. Nato se osredotočimo na teorijo grafov in predstavimo ikozaedersko igro, problem Köningsberv ski mostov, problem prečkanja reke brez mostov in problem v stirih konjev. Kot uvod v obravnavo kitajskih prstanov predstavimo legendo o stolpu iz Brahme in vpeljemo Hanojske stolpe. Dokav zemo optimalno rev sitev Hanojskega stolpa z $n in{mathbb{N}}_0$ diski. Med drugimi predstavimo variacijo Hanojskega stolpa, ki se imenuje zamenjevalni Hanojski stolp in predstavimo zgodovino kitajskih prstanov. Nazadnje problem kitajskih prstanov podrobneje raziščemo in dokav zemo formulo za najhitrejšo rešitev problema. The master’s thesis presents several interesting mathematical puzzles for students. First of all, we deal with various mathematical puzzles throughout the history – such as magic squares and puzzles of the recent times i.e. Rubik’s Cube. In the second part, emphasis is laid on graph theory, where we introduce, the icosian game, the Köningsberg Bridge problem, the problem of crossing the river without bridges, and the problem of four knights. As an introduction to the problem of Chinese rings, we present the legend of the Brahma tower and introduce the Hanoi towers. The optimal solution of the Tower of Hanoi problem with $n in{mathbb{N}}_0$ disks is proven. We also present a variation of Hanoi tower, called switching Tower of Hanoi, and the history of Chinese rings. Finally, we comprehensively investigate the problem of Chinese rings in detail and prove the formula for the fastest solution of the investigated problem.

V magistrskem delu bomo predstavli igro policajev in roparjev na grafih, kjer se policaji in ropar premikajo po vozliščih grafa. Cilj policajev je, da eden izmed njih uspe priti na enako vozlišče kot ropar. Grafom, na katerih ima v igri z enim policajem policaj zmagovalno strategijo, pravimo policaj-zmaga grafi. Najmanjše število policajev, ki je potrebnih, da imajo zmagovalno strategijo na grafu G, imenujemo varnostno število grafa G. Poleg igre policajev in roparjev bomo predstavili še druge različice te igre. Varnostno število grafa bomo izračunali za nekatere preproste družine grafov in predstavili spodnje in zgornje meje varnostnega števila grafa. Nato bomo pokazali, kako varnostno število retraktov grafa vpliva na varnostno število originalnega grafa. Kot bomo videli, retrakti grafov igrajo pomembno vlogo pri karakterizaciji policaj-zmaga grafov. Dokažemo, da so policaj-zmaga grafi natanko odstranljivi grafi. Predstavimo tudi policaj-zmaga urejenost in policaj-zmaga strategijo. Na koncu še dokažemo, da so tudi mostovni grafi policaj-zmaga grafi. In this master's thesis we will present the Game of Cops and Robbers on graphs, where cops and robber moves on vertices of a graph. The goal of the cops is, that one of them is on the same vertex as the robber. The graphs on which one cop has a winning strategy are called cop-win graphs. The minimum number of cops, that have a winning strategy on a graph G, is called the cop number of G. In addition to the Game of Cops and Robbers, we will present other variations of this game. We will calculate the cop number for some simple graph families and present some lower and upper bounds for the cop number. Then we will show how the cop number of a retract of a graph affects on the cop number of the original graph. As we will see, retracts of a graph play an important role in the characterization of the cop-win graphs. We prove that cop-win graphs are exactly dismantlable graphs. Then we present the cop-win ordering and the cop-win strategy. At the end, we show that bridged graphs are cop-win graphs.

V magistrskem delu obravnavamo različne tipe dominacij in sicer dominantno število, neodvisnostno število, neodvisno dominantno število in zgornje dominantno število. Neodvisno dominantno število je raziskano na različnih družinah grafov kot tudi na različnih grafovskih produktih. V prvem delu magistrske naloge smo navedli vse pojme, trditve, izreke, ki jih potrebujemo za razumevanje glavnega problema magistrske naloge. Predstavimo tudi različne razrede grafov in različne dominacije v grafih. V drugem poglavju obravnavamo različne meje neodvisnega dominantnega števila. Predstavljene so splošne meje, ki veljajo na različnih družinah grafov in meje, ki veljajo za dvodelne grafe. Tretje poglavje pa se nanaša na neodvisno dominantno število krepkega, korenskega in kartezičnega produkta. Za nekatere od teh produktov smo prikazali tudi rezultate o neodvisnostnem številu in dominantnem številu. In this Master’s thesis, we discuss different invariants in domination theory. These are: domination number, independent domination number, independence number, upper domination number. We study independent domination number on different graph classes and devote one chapter to independent domination number of graph products. In the first part we list all necessary defnitions, claims and theorems that are needed in the rest of the thesis. We present and define different graph classes and different types of dominations. In the second part we present some bounds for independent domination number in general graphs and also in special graph classes such as bipartite graphs. In the third part we study independent domination number of strong product, rooted product and Cartesian product. For some of those graph products we present also the results on independence and domination number.