Search the digital library catalog

Abstract: Let γ(D) denote the domination number of a digraph D and let C$_m$□C$_n$ denote the Cartesian product of C$_m$ and C$_n$, the directed cycles of length n ≥ m ≥ 3. Liu et al. obtained the exact values of γ(C$_m$□C$_n$) for m up to 6 [Domination number of Cartesian products of directed cycles, Inform. Process. Lett. 111 (2010) 36–39]. Shao et al. determined the exact values of γ(C$_m$□C$_n$) for m = 6, 7 [On the domination number of Cartesian product of two directed cycles, Journal of Applied Mathematics, Volume 2013, Article ID 619695]. Mollard obtained the exact values of γ(C$_m$□C$_n$) for m = 3k + 2 [M. Mollard, On domination of Cartesian product of directed cycles: Results for certain equivalence classes of lengths, Discuss. Math. Graph Theory 33(2) (2013) 387–394.]. In this paper, we extend the current known results on C$_m$□C$_n$ with m up to 21. Moreover, the exact values of γ(C$_n$□C$_n$) with n up to 31 are determined.
Keywords: domination number, Cartesian product, directed cycle
Published in DKUM: 02.09.2022; Views: 611; Downloads: 13
Link to full text

Abstract: Roman domination is a historically inspired variety of general domination such that every vertex is labeled with labels from $\{0,1,2\}$. Roman domination number is the smallest of the sums of labels fulfilling condition that every vertex, labeled 0, has a neighbor, labeled 2. Using algebraic approach we give ▫$O(C)$▫ time algorithm for computing Roman domination number of special classes of polygraphs (rota- and fasciagraphs). By implementing the algorithm we give formulas for Roman domination number of the Cartesian products of paths and cycles ▫$P_n \Box P_k$▫, ▫$P_n \Box C_k$▫ for ▫$k \leq 8$▫ and ▫$n \in {\mathbb N}$▫ and for ▫$C_n \Box P_k$▫ and ▫$C_n \Box C_k$▫ for ▫$k \leq 5$▫, ▫$n \in {\mathbb N}$▫. We also give a list of Roman graphs among investigated families.
Keywords: graph theory, Roman domination number, Cartesian product, polygraphs, path algebra
Published in DKUM: 23.08.2017; Views: 1634; Downloads: 256
Full text (719,06 KB)
This document has many files! More...

Abstract: Rimska dominacija je zgodovinsko utemeljena različica običajne dominacije, pri kateri vozlišča grafa označimo z oznakami iz množice ▫${0,1,2}$▫ tako, da ima vsako vozlišče z oznako 0 soseda z oznako 2. Najmanjšo izmed vsot oznak grafa imenujemo rimsko dominantno število grafa. Z uporabo algebraičnega pristopa dobimo konstantni algoritem za računanje rimskega dominantnega števila posebne vrste poligrafov: rota- in fasciagrafov. V posebnih primerih izračunamo formule za rimsko dominanto število kartezičnega produkta poti in ciklov ▫$P_n Box P_k$▫, ▫$P_n Box C_k$▫ za ▫$k leq 8$▫ in ▫$n in {mathbb N}$▫ ter za ▫$C_n Box P_k$▫ in ▫$C_n Box C_k$▫ za ▫$k leq 5$▫, ▫$n in {mathbb N}$▫. Dodan je seznam rimskih grafov med kartezičnimi produkti zgoraj omenjenih poti in ciklov.
Keywords: teorija grafov, kartezični produkt, rimsko dominantno število, poligrafi, algebra poti, graph theory, Roman domination number, Cartesian product, polygraphs, path algebra
Published in DKUM: 10.07.2015; Views: 1762; Downloads: 75
Link to full text

Abstract: Zapor predstavlja družbo znotraj družbe, ki jo sestavljajo vsi tako ali drugače prisotni v zaporu. Le-ti zato sodelujejo pri vzpostavljanju bolj 'človeške' in ustrezne socialne klime. Življenje in napetost v zaporu ne moreta biti kontrolirana s strogimi formalnimi pravili, potrebni so namreč ustrezni in korektni odnosi med vsemi, ki so del te totalne institucije (Liebling, Price in Shefer, 2011). Največ časa z zaporniki preživijo pravosodni policisti, zato so odnosi med pravosodnimi policisti in zaporniki eden izmed najpomembnejših dejavnikov, ki vplivajo na življenje in delo znotraj zapora. Medsebojno spoštovanje, sklepanje kompromisov in ustrezna komunikacija so pomembni dejavniki za tvorjenje ustreznih odnosov. Za obe strani je vzpostavljanje in vzdrževanje dobrih odnosov težavno zaradi različnih dejavnikov. Pravosodni policisti so primerni tudi za izvajanje pomembnih tretmanskih nalog za resocializacijo, saj zaporniki od osebja najlažje zaupajo pravosodnim policistom. Usposobljenost pravosodnih policistov je zelo pomemben dejavnik, ki pripomore k učinkovitemu in korektnemu izvajanju njihovega dela ter k tvorjenju čim boljših odnosov z zaporniki. Zaradi pomanjkanja pravosodnih policistov pada kakovost in učinkovitost njihovega opravljenega dela ter narašča varnostno tveganje. V primeru dobre socialne klime v zaporu ter dobrih odnosov so primarne naloge pravosodnih policistov lažje izvedljive.
Keywords: zapor, zaporniki, pravosodni policisti, odnosi, socialna klima, diplomske naloge
Published in DKUM: 08.09.2014; Views: 1852; Downloads: 284
Full text (661,39 KB)

Abstract: 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.
Keywords: grafovski produkt, dominacija, algebra poti, konstantni algoritem, mreža, torus
Published in DKUM: 04.04.2013; Views: 2780; Downloads: 227
Full text (1,51 MB)