Back
 OJDM  Vol.7 No.1 , January 2017
On the 2-Domination Number of Complete Grid Graphs
Ramy Shaheen, Suhail Mahfud, Khames Almanea
Show more
Abstract: A set D of vertices of a graph G = (V, E) is called k-dominating if every vertex v ∈V-D is adjacent to some k vertices of D. The k-domination number of a graph G, γk (G), is the order of a smallest k-dominating set of G. In this paper we calculate the k-domination number (for k = 2) of the product of two paths Pm × Pn for m = 1, 2, 3, 4, 5 and arbitrary n. These results were shown an error in the paper [1].
Keywords: k-Dominating Set, k-Domination Number, 2-Dominating Set, 2-Domination Number, Cartesian Product Graphs, Paths
Cite this paper: Shaheen, R. , Mahfud, S. and Almanea, K. (2017) On the 2-Domination Number of Complete Grid Graphs. Open Journal of Discrete Mathematics, 7, 32-50. doi: 10.4236/ojdm.2017.71004.
References

[1]   Mohan, J.J. and Kelkar, I. (2012) Restrained 2-Domination Number of Complete Grid Graphs. International Journal of Applied Mathematics and Computation, 4, 352-358.

[2]   Fink, J.F. and Jacobson, M.S. (1985) n-Domination in graphs, in: Graph Theory with Application to Algorithms and Computer Science. John Wiley and Sons, New York, 282-300.

[3]   Fink, J.F. and Jacobson, M.S. (1985) On n-Domination, n-Dependence and Forbidden Subgraphs. In: Graph Theory with Application to Algorithms and Computer Science, John Wiley and Sons, New York, 301-311.

[4]   Haynes, T.W., Hedetniemi, S.T., Henning, M.A. and Slater, P.J. (2003) H-Forming Sets in Graphs. Discrete Mathematics, 262, 159-169.
https://doi.org/10.1016/S0012-365X(02)00496-X

[5]   Haynes, T.W., Hedetniemi, S.T. and Slater, P.J. (1998) Fundamentals of Domination in Graphs. Marcel Dekker, Inc., New York.

[6]   Hansberg, A. and Volkmann, L. (2009) Upper Bounds on the k-Domination Number and the k-Roman Domination Number. Discrete Applied Mathematics, 157, 1634-1639.
https://doi.org/10.1016/j.dam.2008.10.011

[7]   Cockayne, E.J., Gamble, B. and Shepherd, B. (1985) An Upper Bound for the k-Domination Number of a Graph. Journal of Graph Theory, 9, 533-534.
https://doi.org/10.1002/jgt.3190090414

[8]   Blidia, M., Chellali, M. and Volkmann, L. (2006) Some Bounds on the p-Domination Number in Trees. Discrete Mathematics, 306, 2031-2037.
https://doi.org/10.1016/j.disc.2006.04.010

[9]   Favaron, O., Hansberg, A. and Volkmann, L. (2008) On k-Domination and Minimum Degree in Graphs. Journal of Graph Theory, 57, 33-40.
https://doi.org/10.1002/jgt.20279

[10]   Volkmann, L. (2010) A Bound on the k-Domination Number of a Graph. Czechoslovak Mathematical Journal, 60, 77-83.
https://doi.org/10.1007/s10587-010-0019-1

[11]   Shaheen, R. (2009) Bounds for the 2-Domination Number of Toroidal Grid Graphs. International Journal of Computer Mathematics, 86, 584-588.
https://doi.org/10.1080/00207160701690284

[12]   Shaheen, R. (2013) On the 2-Domination Number of Cartesian Product of Two Cycles. Advances and Applications in Discrete Mathematics, 12, 83-108.

 
 
Top