20.500.12556/DKUM-40005 Algebra poti in dominantni problemi na grafovskih produktih Path algebra and domination problems on graph products Različni problemi grafovskih invariant predstavljajo velik del študij na področju teorije grafov. Ker so ti problemi v veliki meri NP-polni, je smiselno iskati rešitve na določenih zanimivih družinah grafov. V tem delu se omejimo na probleme dominacije na družini poligrafov. To so grafi, ki izhajajo iz kemijske teorije grafov in so matematični model kemijske strukture polimera. V kemiji je polimer makromolekula, ki ima posebno ponavljajočo se strukturo molekul, povezanih s kovalentnimi vezmi. Mi se posebej omejimo na primere, ko so te ponavljajoče enote enake, oziroma v jeziku teorije grafov, ko so monografi izomorfni, ter so povezave med njimi enake. Taki grafi se imenujejo rotagrafi, če pa med prvim in zadnjim monografom ni povezav, imenujemo tak poligraf fasciagraf. S pomočjo algebre poti pokažemo, da se različni problemi dominacije na razredu poligrafov za fiksno velikost monografa lahko rešijo v konstantnem času. Ker so posebni primeri poligrafov tudi grafovski produkti poti in ciklov, za kartezični in direktni produkt implementiramo algoritem in dobimo formule za dominantna, neodvisna dominantna ter rimska dominantna števila teh grafov, kjer je eden od faktorjev fiksen. Nadalje pokažemo, da se preučevane grafovske invariante na fasciagrafih in rotagrafih, pri katerih je monograf enak, lahko razlikujejo le za konstantno vrednost, natančneje, za končno število (različnih) konstant. Nazadnje še rešimo problem rimskega dominantnega števila na leksikografskem produktu grafov. Z vpeljavo koncepta tako imenovanih dominatnih parov za poljubna grafa podamo formulo, ki določi rimsko dominantno število njunega leksikografskega produkta. Podamo tudi nove neskončne družine rimskih grafov. The problem of determining various graph invariants on graphs is one of the major research topics in graph theory. As most of these problems are NP-complete, it is interesting to look for algorithms on different graph classes. In this thesis we will restrict our attention to domination problems on the class of polygraphs. Polygraphs represent a mathematical model for a chemical structure called polymer, that is a molecule, whose structure is composed of multiple repeated units linked by covalent chemical bonds. We will focus on cases where these repeated units are the same, i.e. in graph theoretic terminology, where monographs are isomorphic and edges joining them are the same. Such graphs are known as rotagraphs. If there are no edges between the first and the last copy of the monograph, we refer to such polygraph with the name fasciagraf. Using an algebraic approach we show that many domination problems on the class of polygraphs, where the size of the monograph is fixed, can be solved in constant time. As polygraphs include products of paths and cycles, we implement the algorithm to get closed expressions for the domination, the independent domination and the Roman domination number of the Cartesian and the direct product of paths and cycles, where the size of one factor is fixed. Additionally we show that the values of the investigated graph invariants on the fasciagraphs and the rotagraphs with the same monograph can only differ for a constant value. Using a new concept of the so-called dominating couple we establish the Roman domination number of the lexicographic product of graphs. We also give new infinite classes of Roman graphs among investigated graphs. grafovski produkt dominacija algebra poti konstantni algoritem mreža torus graph product domination path algebra a constant time algorithm grids tori true true false P. Pavlič] Slovenski jezik Angleški jezik Doktorska disertacija 2013-03-26 18:27:20 2013-04-04 14:28:33 2022-05-12 23:21:54 2021-04-22 03:38:45 2013 0 [Maribor 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 519.17(043.3) 19789064 URN:SI:UM:DK:G9UIGGV9 DR_Pavlic_Polona_2013.pdf DR_Pavlic_Polona_2013.pdf 1 3A85A43525F5A485C3548E8B91E76E68 e96503d172277a9dc40a97128b4d954ece2bdb74ce3b5837954c29089cf80c33 41379997-7c09-11eb-bb7a-00155d0001ca 20.500.12556/dkum/1ee39f50-628d-493f-8777-d17b6ec3cb9e https://dk.um.si/Dokument.php?lang=slv&id=54476 Fakulteta za naravoslovje in matematiko 0 0 0