Domination Number of the Complete Directed Grid Graphs

Abstract

We use dynamic programming to compute the domination number of the Cartesian product of two directed paths, ${\overrightarrow{P}}_m$ and ${\overrightarrow{P}}_n$, for $m\le 25$ and all $n$. This suggests that the domination number for $min(m,n)\ge 4$ is $\lfloor \frac{(m+1)(n+1)}{3}\rfloor –1$, which we then confirm by showing that this is both an upper and a lower bound on the domination number.