Pavlič, Polona; Žerovnik, Janez Roman domination number of the Cartesian products of paths and cycles. (English) Zbl 1252.05167 Electron. J. Comb. 19, No. 3, Research Paper P19, 37 p. (2012). Summary: Roman domination is an historically inspired variety of domination in graphs, in which vertices are assigned a value from the set \(\{0,1,2\}\) in such a way that every vertex assigned the value 0 is adjacent to a vertex assigned the value 2. The Roman domination number is the minimum possible sum of all values in such an assignment. Using an algebraic approach we present an \(O(C)\)-time algorithm for computing the Roman domination numbers of special classes of graphs called polygraphs, which include rotagraphs and fasciagraphs. Using this algorithm we determine formulas for the Roman domination numbers of the Cartesian products of the form \(P_n\square P_k\), \(P_n\square C_k\), for \(k\leq8\) and \(n \in {\mathbb N}\), and \(C_n\square P_k\) and \(C_n\square C_k\), for \(k\leq 6\) and \(n \in {\mathbb N}\), for paths \(P_n\) and cycles \(C_n\). We also find all special graphs called Roman graphs in these families of graphs. Cited in 16 Documents MSC: 05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) 05C25 Graphs and abstract algebra (groups, rings, fields, etc.) 05C85 Graph algorithms (graph-theoretic aspects) 68R10 Graph theory (including graph drawing) in computer science Keywords:Roman domination; Cartesian product; polygraphs; algorithm PDFBibTeX XMLCite \textit{P. Pavlič} and \textit{J. Žerovnik}, Electron. J. Comb. 19, No. 3, Research Paper P19, 37 p. (2012; Zbl 1252.05167) Full Text: Link