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\Box P_k$, $P_n\Box C_k$, for $k\leq8$ and $n \in {\mathbb N}$, and $C_n\Box P_k$ and $C_n\Box 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.
@article{10_37236_2595,
author = {Polona Pavli\v{c} and Janez \v{Z}erovnik},
title = {Roman domination number of the {Cartesian} products of paths and cycles},
journal = {The electronic journal of combinatorics},
year = {2012},
volume = {19},
number = {3},
doi = {10.37236/2595},
zbl = {1252.05167},
url = {http://geodesic.mathdoc.fr/articles/10.37236/2595/}
}
TY - JOUR
AU - Polona Pavlič
AU - Janez Žerovnik
TI - Roman domination number of the Cartesian products of paths and cycles
JO - The electronic journal of combinatorics
PY - 2012
VL - 19
IS - 3
UR - http://geodesic.mathdoc.fr/articles/10.37236/2595/
DO - 10.37236/2595
ID - 10_37236_2595
ER -
%0 Journal Article
%A Polona Pavlič
%A Janez Žerovnik
%T Roman domination number of the Cartesian products of paths and cycles
%J The electronic journal of combinatorics
%D 2012
%V 19
%N 3
%U http://geodesic.mathdoc.fr/articles/10.37236/2595/
%R 10.37236/2595
%F 10_37236_2595
Polona Pavlič; Janez Žerovnik. Roman domination number of the Cartesian products of paths and cycles. The electronic journal of combinatorics, Tome 19 (2012) no. 3. doi: 10.37236/2595
