Roman domination number of the Cartesian products of paths and cyclesRepolusk, Polona (Avtor) Žerovnik, Janez (Avtor) graph theoryRoman domination numberCartesian productpolygraphspath algebraRoman 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. Electronic Journal of Combinatorics20122017-08-23 07:29:52Znanstveno delo67551ISSN: 1077-8926UDK: 519.17OceCobissID: 6973785COBISS_ID: 16394585ISSN pri članku: 1077-8926NUK URN: URN:SI:UM:DK:AX7NMELGsl