On independent domination numbers of grid and toroidal grid directed graphs

Document Type : Original paper




A subset $S$ of vertex set $V(D)$ is an  indpendent dominating set of $D$ if $S$ is both an independent and a dominating set of $D$. The  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 cartesian product of two  directed paths $P_m$ and $P_n$ for arbitraries $m$ and $n$. Also, we calculate the independent domination number of the  Cartesian product of two  directed cycles $C_m$ and $C_n$ for $m, n \equiv 0\pmod 3$, and $n \equiv 0\pmod m$. There are many values of $m$ and $n$ such that $C_m \Box C_n$ does not have an independent dominating set.


Main Subjects

[1] S. Ao, E.J. Cockayne, G. MacGillivray, and C.M. Mynhardt, Domination critical graphs with higher independent domination numbers, J. Graph Theory 22 (1996), no. 1, 9–14.
[2] C. Berge, The Theory of Graphs and its Applications, Methuen, London, 1962.
[3] E.J. Cockayne and S.T. Hedetniemi, Independence graphs, Congr. Numer. 10 (1974), 471–491.
[4] E.J. Cockayne and S.T. Hedetniemi, Towards a theory of domination in graphs, Networks 7 (1977), no. 3, 247–261.
[5] J. Haviland, Independent domination in regular graphs, Discrete Math. 143 (1995), no. 1-3, 275–280.
[6] J. Haviland, Upper bounds for independent domination in regular graphs, Discrete Math. 307 (2007), no. 21, 2643–2646.
[7] P. Haxell, B. Seamone, and J. Verstraete, Independent dominating sets and hamiltonian cycles, J. Graph Theory 54 (2007), no. 3, 233–244.
[8] A. Klobučar, Independent sets and independent dominating sets in the strong product of paths and cycles, Math. Commun. 10 (2005), no. 1, 23–30.
[9] A.V. Kostochka, The independent domination number of a cubic 3-connected graph can be much larger than its domination number, Graphs Combin. 9 (1993), no. 2-4, 235–237.
[10] C. Lee, The domination number of a tournament, Kangweon-Kyungki Math. J. 9 (1975), 21–28.
[11] C. Lee, Domination in digraphs, J. Korean Math. Soc. 35 (1998), no. 4, 843–853.
[12] O. Morgenstern, The collaboration between oskar morgenstern and john von neumann on the theory of games, J. Eco. Literat. 14 (1976), no. 3, 805–816.
[13] O. Ore, Theory of Graphs (Amer. Math. Soc. Colloq. Publ. 38), American Mathematical Society, Providence, R. I., 1962.
[14] R. Shaheen, Domination number of toroidal grid digraphs, Util. Math. 78 (2009), 175–184.
[15] R. Shaheen, On the domination number of cartesian products of two directed paths, Int. J. Contemp. Math. Sciences 7 (2012), no. 36, 1785–1790.
[16] R. Shaheen, Total domination number of products of two directed cycles, Util. Math. 92 (2013), 235–250.
[17] Z. Shao, E. Zhu, and F. Lang, On the domination number of cartesian product of two directed cycles, J. Appl. Math. 2013 (2013), Article ID 619695, 7 pages.
[18] J. Southey and M.A. Henning, Domination versus independent domination in cubic graphs, Discrete Math. 313 (2013), no. 11, 1212–1220.