Hop $k$-Rainbow Domination in Graphs

Abstract

Let \( G = (V(G), E(G)) \) be a graph. A function \( f \) that assigns to each vertex \linebreak of $G$ a subset of colors from the set \( \{1, 2, \dots, k\} \), i.e., \( f : V(G) \rightarrow P(\{1, 2, 3, \dots, k\}) \), is called a \textit{hop \( k \)-rainbow dominating function} (H$k$RDF) of \( G \) if for every vertex \( v \in V(G)\) with $f(v)= \varnothing$, we have \( \bigcup_{u \in N^{2}_{G}(v)} f(u) = \{1, 2, \dots, k\} \) where $N^{2}_{G}(v)$ is the set of vertices of $G$ at distance two from $v$. The \textit{weight} of \( f \), denoted \( w(f) \), is defined as \( w(f) = \sum_{x \in V(G)} |f(x)| \). The \textit{hop \( k \)-rainbow domination number} of \( G \), denoted \( \gamma_{hrk}(G) \), is the minimum weight of a hop \( k \)-rainbow dominating function of \( G \). A hop $k$-rainbow dominating function of $G$ with weight $\gamma_{hrk}(G)$ is a $\gamma_{hrk}$-function of $G$. In this paper, we initiate the study of hop \( k \)-rainbow domination in graphs. We begin by exploring fundamental properties of this parameter and then establish various bounds on \( \gamma_{hrk}(G) \). Furthermore, we identify the graphs for which \( \gamma_{hrk}(G) = n \) and determine exact values for certain graph classes, including complete graphs, complete bipartite graphs, paths, and cycles. Additionally, for any positive integer \( a \), we construct connected graphs satisfying \(\gamma_{hr2}(G) = \gamma_{r2}(G) = a.\) Finally, we provide a characterization of all graphs where \( \gamma_{hr2}(G) = n \).