2-Rainbow Domination Number of the Subdivision of Graphs

Articles in Press

Document Type : Original paper

Authors

Department of Mathematics, ‎Faculty of Science, Imam Khomeini International University

Abstract

Let G be a simple graph and f:V(G)→P({1,2}) be a function where for each vertex v∈V(G) with f(v)=∅ we have ⋃u∈NG(v)f(u)={1,2}. Then f is a 2-rainbow dominating function (a 2RDF) of G. The  weight of f is ω(f)=∑v∈V(G)|f(v)|. The minimum weight among all of 2−rainbow dominating functions is 2−rainbow domination number  and is denoted by γr2(G). In this paper,  we provide some bounds for the 2−rainbow domination number of the subdivision graph S(G) of  a graph G. Also, among some other interesting results, we determine the exact value of γr2(S(G)) when G is a tree, a bipartite graph, Kr,s, Kn1,n2,…,nk and Kn.

Keywords

Main Subjects

References

[1] H. Abdollahzadeh Ahangar, M. Chellali, S.M. Sheikholeslami, and J.C. Valenzuela-Tripodoro, On the outer independent total double Roman domination in graphs, Mediterr. J. Math. 20 (2023), no. 3, Article number 171.
https://doi.org/10.1007/s00009-023-02317-1
[2] H. Abdollahzadeh Ahangar, M. Khaibari, N. Jafari Rad, and S.M. Sheikholeslami, Graphs with large total 2-rainbow domination number, Iran. J. Sci. Technol. Trans. A Sci. 42 (2018), 841–846.
https://doi.org/10.1007/s40995-017-0465-9
[3] S. Ahmadi, E. Vatandoost, and A. Behtoei, Domination number and identifying code number of the subdivision graphs, J. Algebraic Sys., to appear.
[4] M. Ali, M. T. Rahim, M. Zeb, and G. Ali, On 2-rainbow domination of some families of graph, Int. J. Math. Soft Comput. 1 (2011), no. 1, 47–53.
[5] A. Behtoei, E. Vatandoost, and F. Azizi Rajol Abad, Signed Roman domination number and join of graphs, J. Algebraic Sys. 4 (2016), no. 1, 65–77.
https://doi.org/10.22044/jas.2016.729
[6] B. Brešar, M.A. Henning, and D. F. Rall, Rainbow domination in graphs, Taiwanese J. Math. 12 (2008), no. 1, 213–225.
http://doi.org/10.11650/twjm/1500602498
[7] B. Brešar and T. K. Šumenjak, On the 2-rainbow domination in graphs, Discrete Appl. Math. 155 (2007), no. 17, 2394–2400.
http://doi.org/10.1016/j.dam.2007.07.018
[8] S. Brezovnik, D.R. Poklukar, and J. Žerovnik, On 2-rainbow domination of generalized Petersen graphs P(ck,k), Mathematics 11 (2023), no. 10, Article ID: 2271.
https://doi.org/10.3390/math11102271
[9] M. Chellali and N. Jafari Rad, On 2-rainbow domination and Roman domination in graphs, Australas. J. Comb. 56 (2013), 85–93.
[10] P. Dankelmann and D. J. Erwin, Distance domination and generalized eccentricity in graphs with given minimum degree, J. Graph Theory 94 (2020), no. 1, 5–19.
https://doi.org/10.1002/jgt.22503
[11] R. Erveš and J. Žerovnik, On 2-rainbow domination number of generalized Petersen graphs P(5k,k), Symmetry 13 (2021), no. 5, Article ID: 809.
https://doi.org/10.3390/sym13050809
[12] A. Ghaffari-Hadigheh, Uncertain weighted dominating set: a prototype application on natural disaster relief managemen, Soft Comput. 22 (2018), 1003–1012.
https://doi.org/10.1007/s00500-016-2404-7.
[13] A. Ghalavand, S. Klavžar, M. Tavakoli, and I.G. Yero, On mixed metric dimension in subdivision, middle, and total graphs, Quaest. Math. 46 (2023), no. 12, 2517–2527.
https://doi.org/10.2989/16073606.2023.2169206
[14] R. Khoeilar, M. Kheibari, M. Chellali, and S.M. Sheikholeslami, A sharp upper bound on the independent 2-rainbow domination in graphs with minimum degree at least two, Comput. Sci. J. Moldova 28 (2020), no. 3, 373–388.
[15] R. Khoeilar, M. Kheibari, Z. Shao, and S.M. Sheikholeslami, Total k-rainbow domination subdivision number in graphs, Comput. Sci. J. Moldova 28 (2020), no. 2, 152–169.
[16] A. Mahmoodi and L. Volkmann, Outer-independent total 2-rainbow dominating functions in graphs, Commun. Comb. Optim. 8 (2023), no. 2, 431–444.
https://doi.org/10.22049/cco.2022.27753.1344
[17] S. M. Mirafzal, Some algebraic properties of the subdivision graph of a graph, Commun. Comb. Optim. 9 (2024), no. 2, 297–307.
https://doi.org/10.22049/cco.2023.28270.1494
[18] D.A. Mojdeh, B. Samadi, Z. Shao, and I.G. Yero, On the outer independent double Roman domination number, Bull. Iranian Math. Soc. 48 (2022), no. 4, 1789–1803.
https://doi.org/10.1007/s41980-021-00606-7
[19] N. Jafari Rad, E. Gholami, A. Tehranian, and H. Rasouli, A new upper bound on the independent 2-rainbow domination number in trees, Commun. Comb. Optim. 8 (2023), no. 1, 261–270.
https://doi.org/10.22049/cco.2022.27641.1305
[20] A. Shaminezhad and E. Vatandoost, On 2-rainbow domination number of functigraph and its complement, Opuscula Math. 40 (2020), no. 5, 617–627.
http://doi.org/10.7494/OpMath.2020.40.5.617
[21] Z. Shao, M. Liang, C. Yin, X. Xu, P. Pavlie, and J. Žerovnik, On rainbow domination number of graphs, Inform. Sci. 254 (2014), 225–230.
https://doi.org/10.1016/j.ins.2013.07.020
[22] X. Shi, P. Wu, Z. Shao, V. Samodivkin, S.M. Sheikholeslami, M. Soroudi, and S. Wang, Changing and unchanging 2-rainbow independent domination, IEEE Access 7 (2019), 72604–72612.
[23] Y. Wu and N. Jafari Rad, Bounds on the 2-rainbow domination of graph, Graphs Combin. 29 (2013), no. 4, 1125–1133.
https://doi.org/10.1007/s00373-012-1158-y
[24] Y. Wu and H. Xing, Note on the 2-rainbow domination and Roman domination in graphs, Appl. Math. Lett. 23 (2010), no. 6, 706–709.
https://doi.org/10.1016/j.aml.2010.02.012
 
Communications in Combinatorics and Optimization

Articles in Press, Accepted Manuscript
Available Online from 31 May 2024

Files

Share

How to cite

Statistics