A function $$f:V(G)\rightarrow \mathcal P (\{1,\ldots ,k\})$$ is called a $$k$$ -rainbow dominating function of $$G$$ (for short $$kRDF$$ of $$G)$$ if $$ \bigcup \nolimits _{u\in N(v)}f(u)=\{1,\ldots ,k\},$$ for each vertex $$ v\in V(G)$$ with $$f(v)=\varnothing .$$ By $$w(f)$$ we mean $$\sum _{v\in V(G)}\left|f(v)\right|$$ and we call it the weight of $$f$$ in $$G.$$ The minimum weight of a $$ kRDF$$ of $$G$$ is called the $$k$$ -rainbow domination number of $$G$$ and it is denoted by $$\gamma _{rk}(G).$$ We ...
This paper studies a variation of domination in graphs called rainbow domination. For a positive integer k, a k-rainbow dominating function of a graph G is a function f from V(G) to the set of all subsets of {1,2,...,k} such that for any vertex v with f(...
A graph $$G$$G is diameter-2-critical if its diameter is two and the deletion of any edge increases the diameter. Murty and Simon conjectured that the number of edges in a diameter-2-critical graph $$G$$G of order $$n$$n is at most $$\lfloor n^2/4 \...
Springer-Verlag
Berlin, Heidelberg