Opuscula Math. 40, no. 5 (2020), 617-627
https://doi.org/10.7494/OpMath.2020.40.5.617
Opuscula Mathematica
On 2-rainbow domination number of functigraph and its complement
Athena Shaminezhad
Ebrahim Vatandoost
Abstract. Let \(G\) be a graph and \(f:V (G)\rightarrow P(\{1,2\})\) be a function where for every vertex \(v\in V(G)\), with \(f(v)=\emptyset\) we have \(\bigcup_{u\in N_{G}(v)} f(u)=\{1,2\}\). Then \(f\) is a \(2\)-rainbow dominating function or a \(2RDF\) of \(G\). The weight of \(f\) is \(\omega(f)=\sum_{v\in V(G)} |f(v)|\). The minimum weight of all \(2\)-rainbow dominating functions is \(2\)-rainbow domination number of \(G\), denoted by \(\gamma_{r2}(G)\). Let \(G_1\) and \(G_2\) be two copies of a graph G with disjoint vertex sets \(V(G_1)\) and \(V(G_2)\), and let \(\sigma\) be a function from \(V(G_1)\) to \(V(G_2)\). We define the functigraph \(C(G,\sigma)\) to be the graph that has the vertex set \(V(C(G,\sigma)) = V(G_1)\cup V(G_2)\), and the edge set \(E(C(G,\sigma)) = E(G_1)\cup E(G_2 \cup \{uv ; u\in V(G_1), v\in V(G_2), v =\sigma(u)\}\). In this paper, \(2\)-rainbow domination number of the functigraph of \(C(G,\sigma)\) and its complement are investigated. We obtain a general bound for \(\gamma_{r2}(C(G,\sigma))\) and we show that this bound is sharp.
Keywords: 2-rainbow domination number, functigraph, complement, cubic graph.
Mathematics Subject Classification: 05C69, 05C75.
- H.A. Ahangar, J. Amjadi, S.M. Sheikholeslami, D. Kuziak, Maximal 2-rainbow domination number of a graph, AKCE Int. J. Graphs Comb. 13 (2016) 2, 157-164.
- J.D. Alvarado, S. Dantas, D. Rautenbach, Averaging 2-rainbow domination and Roman domination, Discrete Appl. Math. 205 (2016), 202-207.
- B. Bresar, M.A. Henning, D.F. Rall, Rainbow domination in graphs, Taiwanese J. Math. 12 (2008) 1, 213-225.
- B. Bresar, T.K. Sumenjak, On the 2-rainbow domination in graphs, Discrete Appl. Math. 155 (2007) 17, 2349-2400.
- G.J. Chang, J. Wu, X. Zhu, Rainbow domination on trees, Discrete Appl. Math. 158 (2010) 1, 8-12.
- S. Fujita, M. Furuya, Difference between 2-rainbow domination and Roman domination in graphs, Discrete Appl. Math. 161 (2013) 6, 806-812.
- M. Furuya, A note on total domination and 2-rainbow domination in graphs, Discrete Appl. Math. 184 (2015), 229-230.
- F. Ramezani, E.D. Rodrguez-Bazan, J.A. Rodrguez-Velazquez, On the Roman domination number of generalized Sierpinski graphs, Filomat 31:20 (2017), 6515-6528.
- Z. Shao, H. Jiang, P. Wu, S. Wang, J. Žerovnik, X. Zhang, J.B. Liu, On 2-rainbow domination of generalized Petersen graphs, Discrete Appl. Math. 257 (2019), 370-384.
- Z. Stepien, M. Zwierzchowski, 2-rainbow domination number of Cartesian products: \(C_{n}\square C_{3}\) and \(C_ {n}\square C_{5}\), J. Comb. Optim. 28 (2014) 4, 748-755.
- T.K. Sumenjak, D.F. Rall, A. Tepeh, On \(k\)-rainbow independent domination in graphs, Appl. Math. Comput. 333 (2018), 353-361.
- E. Vatandoost, F. Ramezani, Domination and signed domination number of Cayley graphs, Iran. J. Math. Sci. Inform. 14 (2019) 1, 35-42.
- Y. Wang, X. Wu, N. Dehgardi, J. Amjadi, R. Khoeilar, J.B. Liu, \(k\)-rainbow domination number of \(P_{3} \square P_{n}\), Mathematics 7 (2019) 2, 203.
- D.B. West, Introduction to Graph Theory, vol. 2, Upper Saddle River, NJ: Prentice Hall, 1996.
- Y. Wu, N.J. Rad, Bounds on the 2-rainbow domination number of graphs, Graphs Combin. 29 (2013) 4, 1125-1133.
- K.H. Wu, Y.L. Wang, C.C. Hsu, C.C. Shih, On 2-rainbow domination in generalized Petersen graphs, Int. J. Comput. Math. Comput. Syst. Theory 2 (2017) 1, 1-13.
- Y. Wu, H. Xing, Note on 2-rainbow domination and Roman domination in graphs, Appl. Math. Lett. 23 (2010) 6, 706-709.
- Athena Shaminezhad
- Imam Khomeini International University, Department of Basic Science, Nouroozian Street, Qazvin, Iran
- Ebrahim Vatandoost (corresponding author)
- Imam Khomeini International University, Department of Basic Science, Nouroozian Street, Qazvin, Iran
- Communicated by Dalibor Fronček.
- Received: 2020-01-06.
- Revised: 2020-06-04.
- Accepted: 2020-07-07.
- Published online: 2020-10-10.
