On k-rainbow domination in middle graphs

Department of Mathematics, Pusan National University, Busan 46241, Republic of Korea

^* Corresponding author: knukkj@pusan.ac.kr

Received: 17 February 2021
Accepted: 24 October 2021

Abstract

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.