On k-rainbow domination in middle graphs
Kijung Kim · RAIRO - Operations Research · 2021
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 ⋃u∈N(v) f(u) = {1,2,…,k}. The weight of a k-rainbow dominating function is the value ∑v∈V(G)|f(v)|. The k-rainbow domination number γrk (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.