On independent domination numbers of grid and toroidal grid directed graphs

Document Type : Original paper

Author

ٍSyrian

Abstract

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 Pm and Pn for arbitraries m and n. Also, we calculate the independent domination number of the  Cartesian product of two  directed cycles Cm and Cn for m,n≡0(mod3), and n≡0(modm). There are many values of m and n such that Cm◻Cn does not have an independent dominating set.

Keywords

Main Subjects

References

[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.
 
Communications in Combinatorics and Optimization
Volume 4, Issue 1
June 2019
Pages 71-77

Files

Share

How to cite

Statistics