Discussiones Mathematicae Graph Theory 33(2) (2013) 387-394
doi: 10.7151/dmgt.1668

[BIBTex] [PDF] [PS]

On the domination of Cartesian product of directed cycles: Results for certain equivalence classes of lengths

Michel Mollard

CNRS Université Joseph Fourier
Institut Fourier
100, rue des Maths
38402 St Martin d'Héres Cedex France

Abstract

Let γ(CmCn) be the domination number of the Cartesian product of directed cycles Cm and Cn for m,n ≥ 2. Shaheen [13] and Liu et al. ([11], [12]) determined the value of γ(CmCn) when m ≤ 6 and [12] when both m and n ≡ 0 (mod 3). In this article we give, in general, the value of γ(CmCn) when m ≡ 2(mod 3) and improve the known lower bounds for most of the remaining cases. We also disprove the conjectured formula for the case m ≡ 0(mod 3) appearing in [12].

Keywords: directed graph, Cartesian product, domination number, directed cycle

2010 Mathematics Subject Classification: 05C69,05C38.

References

[1]T.Y. Chang and W.E. Clark, The domination numbers of the 5 × n and 6 × n grid graphs, J. Graph Theory 17 (1993) 81--107, doi: 10.1002/jgt.3190170110.
[2]M. El-Zahar and C.M. Pareek, Domination number of products of graphs, Ars Combin. 31 (1991) 223--227.
[3]M. El-Zahar, S. Khamis and Kh. Nazzal, On the domination number of the Cartesian product of the cycle of length n and any graph, Discrete Appl. Math. 155 (2007) 515--522, doi: 10.1016/j.dam.2006.07.003.
[4]R.J. Faudree and R.H. Schelp, The domination number for the product of graphs, Congr. Numer. 79 (1990) 29--33.
[5]S. Gravier and M. Mollard, On domination numbers of Cartesian product of paths, Discrete Appl. Math. 80 (1997) 247--250, doi: 10.1016/S0166-218X(97)00091-7.
[6]B. Hartnell and D. Rall, On dominating the Cartesian product of a graph and K2, Discuss. Math. Graph Theory 24 (2004) 389--402, doi: 10.7151/dmgt.1238.
[7]T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs ( Marcel Dekker, Inc. New York, 1998).
[8]T.W. Haynes, S.T. Hedetniemi and P.J. Slater , Domination in Graphs: Advanced Topics (Marcel Dekker, Inc. New York, 1998).
[9]M.S. Jacobson and L.F. Kinch, On the domination number of products of graphs I, Ars Combin. 18 (1983) 33--44.
[10]S. Klavžar and N. Seifter, Dominating Cartesian products of cycles, Discrete Appl. Math. 59 (1995) 129--136, doi: 10.1016/0166-218X(93)E0167-W.
[11]J. Liu, X.D. Zhang, X. Chenand and J. Meng, On domination number of Cartesian product of directed cycles, Inform. Process. Lett. 110 (2010) 171--173, doi: 10.1016/j.ipl.2009.11.005.
[12]J. Liu, X.D. Zhang, X. Chen and J. Meng, Domination number of Cartesian products of directed cycles, Inform. Process. Lett. 111 (2010) 36--39, doi: 10.1016/j.ipl.2010.10.001.
[13]R.S. Shaheen, Domination number of toroidal grid digraphs, Util. Math. 78 (2009) 175--184.

Received 8 April 2011
Revised 24 May 2012
Accepted 28 May 2012