The domination number of \(K_n^3\). (English) Zbl 1305.05175

Summary: Let \(K_n^3\) denote the Cartesian product \(K_n\square K_n\square K_n\), where \(K_n\) is the complete graph on \(n\) vertices. We show that the domination number of \(K_n^3\) is \(\lceil\frac{n^2}{2}\rceil\).


05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05C76 Graph operations (line graphs, products, etc.)
Full Text: DOI


[1] T.Y. Chang, Domination number of grid graphs, Ph.D. Thesis, (Department of Mathematics, University of South Florida, 1992).
[2] 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-108. doi:10.1002/jgt.3190170110 · Zbl 0780.05030
[3] M.H. El-Zahar and R.S. Shaheen, On the domination number of the product of two cycles, Ars Combin. 84 (2007) 51-64. · Zbl 1212.05192
[4] M.H. El-Zahar and R.S. Shaheen, The domination number of C8 □Cn and C9 □Cn, J. Egyptian Math. Soc. 7 (1999) 151-166. · Zbl 0935.05070
[5] D. Gon¸calves, A. Pinlou, M. Rao and S. Thomass´e, The domination number of grids, SIAM J. Discrete Math. 25 (2011) 1443-1453. doi:10.1137/11082574 · Zbl 1237.05150
[6] F. Harary and M. Livingston, Independent domination in hypercubes, Appl. Math. Lett. 6 (1993) 27-28. doi:10.1016/0893-9659(93)90027-K · Zbl 0780.05031
[7] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker, 1998). · Zbl 0890.05002
[8] M.S. Jacobson and L.F. Kinch, On the domination number of the products of graphs I, Ars Combin. 18 (1983) 33-44. · Zbl 0566.05050
[9] S. Klavˇzar and N. Seifter, Dominating Cartesian products of cycles, Discrete Appl. Math. 59 (1995) 129-136. doi:10.1016/0166-218X(93)E0167-W · Zbl 0824.05037
[10] K.-J. Pai and W.-J. Chiu, A note on “On the power dominating set of hypercubes”, in: Proceedings of the 29th Workshop on Combinatorial Mathematics and Comput- ing Theory, National Taipei College of Business, Taipei, Taiwan April 27-28, (2012) 65-68.
[11] R.S. Shaheen, On the domination number of m × n toroidal grid graphs, Congr. Numer. 146 (2000) 187-200. · Zbl 0976.05045
[12] V.G Vizing, Some unsolved problems in graph theory, Uspekhi Mat. Nauk, 23 (6 (144)) (1968) 117-134. · Zbl 0177.52301
[13] V.G Vizing, The Cartesian product of graphs, Vy˘cisl. Sistemy 9 (1963) 30-43.
[14] D.B. West, Introduction to Graph Theory (Prentice Hall, 2001)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.