Rainbow domination and related problems on strongly chordal graphs
Journal
Discrete Applied Mathematics
Journal Volume
161
Journal Issue
10-11
Pages
1395-1401
Date Issued
2013
Author(s)
Abstract
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:V(G)→2{1,2,.,k} such that ∪u∈NG (v)f(u)={1,2,.,k} for any vertex v with f(v)=Combining long solidus overlay. The k-rainbow domination number γrk(G) of G is the minimum value of ∑v∈V(G)|f(v)|, where f runs over all k-rainbow dominating functions of G. A related concept is as follows. A weak {k}-dominating function of G is a function g:V(G)→{0,1,2,.,k} such that ∑u∈NG (v)g(u)≥k for any vertex v with g(v)=0. The weak {k}-domination number γwk(G) of G is the minimum value of ∑v∈V(G)g(v), where g runs over all weak {k}-dominating functions of G. In this paper, we prove that γwk(G)= γrk(G) for any strongly chordal graph G. Our approach is a more general setting called the k-function, which leads to interesting results on other variations of domination. We also give a linear-time algorithm for finding the weak {k}-domination numbers of block graphs. © © 2013 Elsevier B.V. All rights reserved.
Type
journal article