A Note on the Domination Number of the Cartesian Products of Paths and Cycles


Polona Pavlič, Janez Žerovnik




Using algebraic approach we implement a constant time algorithm for computing the domination numbers of the Cartesian products of paths and cycles. Closed formulas are given for domination numbers $\gamma(P_n\Box C_k)$ (for $k\leq 11$, $n \in {\mathbb N}$) and domination numbers $\gamma(C_n\Box P_k)$ and $\gamma(C_n\Box C_k)$ (for $k\leq7$, $n \in {\mathbb N}$).