no. 6
On k -rainbow domination in middle graphs
RAIRO. Operations Research, Tome 55 (2021) no. 6, pp. 3447-3458

Let G be a finite simple graph with vertex set V(G) and edge set E(G). A function f : V(G) → P({1,2,…,k}) is a k-rainbow dominating function on G if for each vertex v∈V(G) for which f(v) = ∅, it holds that ⋃$$ f(u) = {1,2,…,k}. The weight of a k-rainbow dominating function is the value ∑$$|f(v)|. The k-rainbow domination number γ$$ (G) is the minimum weight of a k-rainbow dominating function on G. In this paper, we initiate the study of k-rainbow domination numbers in middle graphs. We define the concept of a middle k-rainbow dominating function, obtain some bounds related to it and determine the middle 3-rainbow domination number of some classes of graphs. We also provide upper and lower bounds for the middle 3-rainbow domination number of trees in terms of the matching number. In addition, we determine the 3-rainbow domatic number for the middle graph of paths and cycles.

DOI : 10.1051/ro/2021163
Classification : 05C69
Keywords: $$-rainbow domination number, middle graph, middle $$-rainbow domination number, matching number, $$-rainbow domatic number 
@article{RO_2021__55_6_3447_0,
     author = {Kim, Kijung},
     title = {On $k$-rainbow domination in middle graphs},
     journal = {RAIRO. Operations Research},
     pages = {3447--3458},
     year = {2021},
     publisher = {EDP-Sciences},
     volume = {55},
     number = {6},
     doi = {10.1051/ro/2021163},
     mrnumber = {4338795},
     zbl = {1483.05121},
     language = {en},
     url = {https://www.numdam.org/articles/10.1051/ro/2021163/}
}
TY  - JOUR
AU  - Kim, Kijung
TI  - On $k$-rainbow domination in middle graphs
JO  - RAIRO. Operations Research
PY  - 2021
SP  - 3447
EP  - 3458
VL  - 55
IS  - 6
PB  - EDP-Sciences
UR  - https://www.numdam.org/articles/10.1051/ro/2021163/
DO  - 10.1051/ro/2021163
LA  - en
ID  - RO_2021__55_6_3447_0
ER  - 
%0 Journal Article
%A Kim, Kijung
%T On $k$-rainbow domination in middle graphs
%J RAIRO. Operations Research
%D 2021
%P 3447-3458
%V 55
%N 6
%I EDP-Sciences
%U https://www.numdam.org/articles/10.1051/ro/2021163/
%R 10.1051/ro/2021163
%G en
%F RO_2021__55_6_3447_0
Kim, Kijung. On $k$-rainbow domination in middle graphs. RAIRO. Operations Research, Tome 55 (2021) no. 6, pp. 3447-3458. doi: 10.1051/ro/2021163

[1] J. A. Bondy and U. S. R. Murty, Graph Theory. Vol. 244 of Graduate Texts in Mathematics. Springer (2007). | MR | Zbl

[2] B. Brešar, Rainbow domination in graphs. In: Topics in Domination in Graphs, edited by T. W. Haynes, S. T. Hedetniemi and M. A. Henning. Springer International Publishing, Switzerland (2020). | DOI

[3] B. Brešar, M. A. Henning and D. F. Rall, Rainbow domination in graphs. Taiwanese J. Math. 12 (2008) 213–225. | MR | Zbl | DOI

[4] G. J. Chang, J. J. Wu and X. D. Zhu, Rainbow domination on trees. Discrete Appl. Math. 158 (2010) 8–12. | MR | Zbl | DOI

[5] V. J. A. Cynthia and A. Kavitha, On 2 and 3 -rainbow domination number of circulant graph G ( n ; { 1 , 2 , 3 } ) . Int. J. Math. Comput. Sci. 15 (2020) 661–670. | MR | Zbl

[6] M. Furuya, M. Koyanagi and M. Yokota, Upper bound on 3 -rainbow domination in graphs with minimum degree 2 . Discrete Optim. 29 (2018) 45–76. | MR | Zbl | DOI

[7] H. Gao, C. Xi and Y. Yang, The 3 -rainbow domination number of the cartesian product of cycles. Mathematics 8 (2020) 65. | DOI

[8] T. Hamada and I. Yoshimura, Traversability and connectivity of the middle graph of a graph. Discrete Math. 14 (1976) 247–255. | MR | Zbl | DOI

[9] K. Kim, Italian, 2 -rainbow and Roman domination numbers in middle graphs, Submitted. | MR | Zbl | DOI

[10] Z. H. Shao, M. L. Liang, C. Yin, X. D. Xu, P. Pavlič and J. Žerovnik, On rainbow domination numbers of graphs. Inf. Sci. 254 (2014) 225–234. | MR | Zbl | DOI

[11] S. M. Sheikholeslami and L. Volkmann, The k -rainbow domatic number of a graph. Discuss. Math. Graph Theory 32 (2012) 129–140. | MR | Zbl | DOI

[12] Y. Wang, X. L. Wu, N. Dehgardi, J. Amjadi, R. Khoeilar and J. B. Liu, k -rainbow domination number of P 3 □ P n . Mathematics 7 (2019) 203. | DOI

Cité par Sources :