On independent domination numbers of grid and toroidal grid directed graphs

Abstract

A subset $S$ of vertex set $V(D)$ is an {em indpendent dominating set} of $D$ if $S$ is both an independent and a dominating set of $D$. The {em indpendent domination number}, $i(D)$ is the cardinality of the smallest independent dominating set of $D$. In this paper we calculate the independent domination number of the { em cartesian product} of two {em directed paths} $P_m$ and $P_n$ for arbitraries $m$ and $n$. Also, we calculate the independent domination number of the { em cartesian product} of two {em directed cycles} $C_m$ and $C_n$ for $m, n equiv 0 ({rm mod} 3)$, and $n equiv 0 ({rm mod} m)$. There are many values of $m$ and $n$ such that $C_m Box C_n$ does not have an independent dominating set.