On 4-domination and 4-rainbow domination of cylindrical graphs

Articles in Press

Document Type : Original paper

Author

1 FME, University of Ljubljana, Aškerčeva 6, Ljubljana, 1000, Slovenia

2 Rudolfovo - Science and Technology Centre Novo Mesto, Podbreznik 15, Novo mesto, 8000, Slovenia

Abstract

Cylindrical graphs and torus grid graphs are naturally constructed from sub-graphs of the infinite grid by certain identifications of boundary vertices. Considering various domination type problems, it is usually possible to find an optimal solution on the infinite grid. To the contrary, exact values of invariants for the cylindrical and torus grid graphs are typically only known for special subfamilies, and are in general hard to compute. The 4-domination and 4-rainbow domination of cylindrical graphs is studied, and some new formulae and improved bounds are reported, generalizing recent results for the case $k = 2$ in [Computational and Applied Mathematics 44(5), 293 (2025)]. We also consider weak 4-domination and singleton 4-rainbow domination.

Keywords

Main Subjects

References

[1] B. Brešar, Rainbow domination in graphs, Topics in Domination in Graphs (Cham) (T.W. Haynes, S.T. Hedetniemi, and M.A. Henning, eds.), Springer International Publishing, 2020, pp. 411–443.
[2] B. Brevar, M.A. Henning, and D.F. Rall, Rainbow domination in graphs, Taiwanese J. Math. 12 (2008), no. 1, 213–225.
https://doi.org/10.11650/twjm/1500602498
[3] S. Brezovnik, D. Rupnik Poklukar, and J. Žerovnik, The 2-rainbow domination number of cartesian bundles over cycles, CEJOR Cent. Eur. J. Oper. Res. 33 (2025), no. 3, 641–659. https://doi.org/10.1007/s10100-024-00949-6
[4]  S. Brezovnik, D. Rupnik Poklukar, and J. Žerovnik, The 2-rainbow domination number of cartesian product of cycles, Ars Math. Contemp. 25 (2025), no. 3, #P3.04. https://doi.org/10.26493/1855-3974.3168.74d
[5] J.J. Carreño, J.A. MartÍnez, and M.L. Puertas, A general lower bound for the domination number of cylindrical graphs, Bull. Malays. Math. Sci. Soc. 43 (2020), no. 2, 1671–1684. https://doi.org/10.1007/s40840-019-00765-1
[6] R. Erveš and J. Žerovnik, On 3-rainbow domination number of generalized petersen graphs $P(6k, k)$, Symmetry 13 (2021), no. 10, 1860. https://doi.org/10.3390/sym13101860
[7] J.F. Fink and M.S. Jacobson, n-domination in graphs, Graph Theory with Applications to Algorithms and Computer Science (USA), John Wiley & Sons, Inc., 1985, pp. 283–300. https://api.semanticscholar.org/CorpusID:118533627
[8] H. Gao, K. Li, and Y. Yang, The $k$-rainbow domination number of $C_n\Box C_m$, Mathematics 7 (2019), no. 12, 1153. https://doi.org/10.3390/math7121153
[9] H. Gao, C. Xi, and Y. Yang, The 3-rainbow domination number of the Cartesian product of cycles, Mathematics 8 (2020), no. 1, 65. https://doi.org/10.3390/math8010065
[10] H. Gao, Y. Zhang, Y. Wang, Y. Guo, X. Liu, R. Liu, C. Xi, and Y. Yang, Rainbow domination in Cartesian product of paths and cycles, Internat. J. Found. Comput. Sci. 35 (2024), no. 8, 907–928. https://doi.org/10.1142/S0129054123500272
[11] E.M. Garzón, J.A. MartÍnez, J.J. Moreno, and M.L. Puertas, Hpc acceleration of large $(min,+)$ matrix products to compute domination-type parameters in graphs, J. Supercomput. 78 (2022), no. 16, 17826–17843. https://doi.org/10.1007/s11227-022-04574-5
[12] E.M. Garzón, J.A. MartÍnez, J.J. Moreno, and M.L. Puertas, On the 2-domination number of cylinders with small cycles, Fund. Inform. 185 (2022), no. 2, 185–199. https://doi.org/10.3233/FI-222107
[13] D.R. Guichard, A new lower bound for the domination number of complete cylindrical grid graphs, J. Comb. Math. Comb. Comput. 120 (2024), 411–416. https://doi.org/10.61091/jcmcc120-38
[14] R.H. Hammack, W. Imrich, and S. Klavžar, Handbook of Product Graphs, vol. 2, CRC press Boca Raton, 2011.
[15] T.W. Haynes, S. Hedetniemi, and P. Slater, Fundamentals of Domination in Graphs, CRC press, 2013.
[16] T.W. Haynes, S.T. Hedetniemi, and M.A. Henning, Topics in Domination in Graphs, vol. 64, Springer, 2020.
[17] S. Klavžar and J. Žerovnik, Algebraic approach to fasciagraphs and rotagraphs, Discrete Appl. Math. 68 (1996), no. 1-2, 93–100. https://doi.org/10.1016/0166-218X(95)00058-Y
[18] J.A. MartÍnez, A.B. Castaño-Fernández, and M.L. Puertas, The 2-domination number of cylindrical graphs, Comput. Appl. Math. 41 (2022), no. 8, 424. https://doi.org/10.1007/s40314-022-02137-1
[19] M. Nandi, S. Parui, and A. Adhikari, The domination numbers of cylindrical grid graphs, Appl. Math. Comput. 217 (2011), no. 10, 4879–4889. https://doi.org/10.1016/j.amc.2010.11.019
[20] T. Pisanski, J. Shawe-Taylor, and J. Vrabec, Edge-colorability of graph bundles, J. Comb. Theory, B 35 (1983), no. 1, 12–19. https://doi.org/10.1016/0095-8956(83)90076-X
[21] E. Sampathkumar and L.P. Latha, Strong weak domination and domination balance in a graph, Discrete Math. 161 (1996), no. 1-3, 235–242. https://doi.org/10.1016/0012-365X(95)00231-K
[22] Z. Shao, Z. Li, R. Erveš, and J. Žerovnik, The 2-rainbow domination numbers of $C_4\Box C_n$ and $C_8\Box C_n$, Nat. Acad. Sci. Lett. 42 (2019), no. 5, 411–418. https://doi.org/10.1007/s40009-018-0779-y
[23] J. Žerovnik, On 2-domination and 2-rainbow domination of cylindrical graphs, Comput. Appl. Math. 44 (2025), no. 5, 239. https://doi.org/10.1007/s40314-025-03201-2
Communications in Combinatorics and Optimization

Articles in Press, Accepted Manuscript
Available Online from 05 December 2025

Files

Share

How to cite

Statistics