A set D of vertices of a graph G = (V, E) is called k-dominating if every vertexv ∈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].
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.
