20.500.12556/DKUM-67551 Roman domination number of the Cartesian products of paths and cycles Rimsko dominantno število kartezičnega produkta poti in ciklov 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. 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. graph theory Roman domination number Cartesian product polygraphs path algebra teorija grafov kartezični produkt rimsko dominantno število poligrafi algebra poti true true true Electronic Journal of Combinatorics Angleški jezik Slovenski jezik Znanstveno delo 2017-08-23 07:29:52 2017-08-23 07:31:49 2026-09-03 13:56:38 2019-07-11 16:17:49 2012 0 0 str. 1-37 št. 3 Letn. 19 2012 0000-00-00 Zaloznikova Objavljeno NiDoloceno 2011-01-16 2012-08-01 2012-08-09 1077-8926 519.17 6973785 16394585 1077-8926 URN:SI:UM:DK:AX7NMELG Electronic_Journal_of_Combinatorics_2012_Repolusk,_Zerovnik_Roman_domination_number_of_the_Cartesian_products_of_paths_and_cycles.pdf Electronic_Journal_of_Combinatorics_2012_Repolusk,_Zerovnik_Roman_domination_number_of_the_Cartesian_products_of_paths_and_cycles.pdf 1 7B6681AABE2A4F6CEDF9F32D19F96E25 8ce137a3148a25d286d4a3e1284649faccd27118da9a6619e7f55dc0abaf5bb8 8ab43673-7c0e-11eb-bb7a-00155d0001ca 20.500.12556/dkum/937b65a6-8179-41f3-a998-533d6188b981 https://dk.um.si/Dokument.php?lang=slv&id=115741 http://www.combinatorics.org/ojs/index.php/eljc/article/view/v19i3p19 1 https://dk.um.si/Dokument.php?lang=slv&id=115740 Fakulteta za naravoslovje in matematiko 0 0 0