Research ArticleOpen AccessGoogle Scholar indexed
On the 2-Domination Number of Complete Grid Graphs
Department of Mathematics, Faculty of Science, Tishreen University, Lattakia, Syria
Department of Mathematics, Faculty of Science, Tishreen University, Lattakia, Syria
Department of Mathematics, Faculty of Science, Tishreen University, Lattakia, Syria
- 1 Department of Mathematics, Faculty of Science, Tishreen University, Lattakia, Syria
- 2 Department of Mathematics, Faculty of Science, Tishreen University, Lattakia, Syria
- 3 Department of Mathematics, Faculty of Science, Tishreen University, Lattakia, Syria
Open Journal of Discrete Mathematics·Volume 07 (2016)·Pages 32–50·Published 6 December 2016·DOI10.4236/ojdm.2017.71004
Copy link · social · email
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 P m × P n for m = 1, 2, 3, 4, 5 and arbitrary n. These results were shown an error in the paper [1].
Keywords<i>k</i>-Dominating Set<i>k</i>-Domination Number2-Dominating Set2-Domination NumberCartesian Product GraphsPaths
- 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.
- 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.
- 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.
- 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
- Haynes, T.W., Hedetniemi, S.T. and Slater, P.J. (1998) Fundamentals of Domination in Graphs. Marcel Dekker, Inc., New York.
- 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
- 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
- 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
- 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
- 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
- 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
- Shaheen, R. (2013) On the 2-Domination Number of Cartesian Product of Two Cycles. Advances and Applications in Discrete Mathematics, 12, 83-108.