# Rainbow Domination and Related Problems on Some Classes of Perfect Graphs

Wing-Kai Hon, Ton Kloks, Hsiang-Hsuan Liu, Hung-Lung Wang

► To cite this version:

Wing-Kai Hon, Ton Kloks, Hsiang-Hsuan Liu, Hung-Lung Wang. Rainbow Domination and Related Problems on Some Classes of Perfect Graphs. 1st International Conference on Theoretical Computer Science (TTCS), Aug 2015, Tehran, Iran. pp.121-134, 10.1007/978-3-319-28678-5_9 . hal-01446271

HAL Id: hal-01446271

https://inria.hal.science/hal-01446271

Submitted on 25 Jan 2017

**HAL** is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
RAINBOW DOMINATION AND RELATED PROBLEMS ON
SOME CLASSES OF PERFECT GRAPHS

Wing-Kai Hon¹, Ton Kloks, Hsiang-Hsuan Liu¹,², and Hung-Lung Wang³

¹ Department of Computer Science
National Tsing Hua University, Taiwan
{wkhon, hhliu}@cs.nthu.edu.tw

² University of Liverpool
hhliu@liv.ac.uk

³ Institute of Information and Decision Sciences
National Taipei University of Business, Taiwan
hlwang@ntub.edu.tw

**Abstract.** Let $k \in \mathbb{N}$ and let $G$ be a graph. A function $f: V(G) \to 2^{[k]}$ is a rainbow function if, for every vertex $x$ with $f(x) = \emptyset$, $f(N(x)) = [k]$, where $[k]$ denotes the integers ranging from 1 to $k$. The rainbow domination number $\gamma_{kr}(G)$ is the minimum of $\sum_{x \in V(G)} |f(x)|$ over all rainbow functions. We investigate the rainbow domination problem for some classes of perfect graphs.

# 1 Introduction

In 2008, Brešar et al. [2] introduced the *k*-rainbow domination problem, which is a generalized formulation of graph domination. In the graph domination problem, a set of vertices is selected as the “guards” such that each vertex not selected has a guard as a neighbor; while in the *k*-rainbow domination problem, *k* different types of guards are required in the neighborhood of a non-selected vertex. The *k*-rainbow domination-problem drew our attention because it is solvable in polynomial time for classes of graphs of bounded rankwidth but, unless one fixes *k* as a constant, it seems not formulatable in monadic second-order logic. Let us start with the definition.

**Definition 1.** Let $k \in \mathbb{N}$ and let $G$ be a graph. A function $f: V(G) \to 2^{[k]}$ is a *k*-rainbow function if, for every $x \in V(G)$,

$$f(x) = \emptyset \text{ implies } \cup_{y \in N(x)} f(y) = [k].$$

The *k*-rainbow domination number of *G* is

$$\gamma_{rk}(G) = \min \{ \|f\| \mid f \text{ is a } k\text{-rainbow function for } G \}, \\ \text{where } \|f\| = \sum_{x \in V(G)} |f(x)|.$$
We call $\|f\|$ the cost of $f$ over the graph $G$. When there is danger of confusion, we write $\|f\|_G$ instead of $\|f\|$. We call the elements of $[k]$ the colors of the rainbow and, for a vertex $x$ we call $f(x)$ the label of $x$. For a set $S$ of vertices we write

$$f(S) = \cup_{x \in S} f(x).$$

It is a common phenomenon that the introduction of a new domination variant is followed chop-chop by an explosion of research results and their write-ups. One reason for the popularity of domination problems is the wide range of applicability and directions of possible research. We leave our bibliography of recent publications on this specific domination variant to the full version of this paper [20]. We refer to [28] for the description of an application of rainbow domination.

To begin with, Brešar et al. showed that, for any graph $G$,

$$\gamma_{rk}(G) = \gamma(G \square K_k), \qquad (1)$$

where $\gamma$ denotes the domination number and where $\square$ denotes the Cartesian product. This observation, together with Vizing's conjecture, stimulated the search for graphs for which $\gamma = \gamma_{r2}$ (see also [1, 21]). Notice that, by (1) and Vizing's upperbound $\gamma_{rk}(G) \le k \cdot \gamma(G)$ [29].

Chang et al. [7] were quick on the uptake and showed that, for $k \in \mathbb{N}$, the $k$-rainbow domination problem is NP-complete, even when restricted to chordal graphs or bipartite graphs. The same paper shows that there is a linear-time algorithm to determine the parameter on trees. A similar algorithm for trees appears in [30] and this paper also shows that the problem remains NP-complete on planar graphs.

Notice that (1) shows that $\gamma_{rk}(G)$ is a non-decreasing function in $k$. Chang et al. show that, for all graphs $G$ with $n$ vertices and all $k \in \mathbb{N}$,

$$\min \{k, n\} \le \gamma_{rk}(G) \le n \quad \text{and} \quad \gamma_{rn}(G) = n.$$

For trees $T$, Chang et al. [7] give sharp bounds for the smallest $k$ satisfying $\gamma_{rk}(T) = |V(T)|$.

Many other papers establish bounds and relations, eg, between the 2-rainbow domination number and the total domination number or the (weak) roman domination number, or study edge- or vertex critical graphs with respect to rainbow domination, or obtain results for special graphs such as paths, cycles, graphs with given radius, and the generalized Petersen graphs. A detailed survey can be found in [20].

Pai and Chiu [23] develop an exact algorithm and a heuristic for 3-rainbow domination. They present the results of some experiments. Let us mention
that the k-rainbow domination number may be computed, via (1), by an exact, exponential algorithm that computes the domination number. For example, this shows that the k-rainbow domination number can be computed in $O(1.4969^{nk})$ [24, 25].

Whenever domination problems are under investigation, the class of strongly chordal graphs are of interest from a computational point of view. Farber showed that a minimum weight dominating set can be computed in polynomial time on strongly chordal graphs [14]. Recently, Chang et al. showed that the k-rainbow dominating number is equal to the so-called weak {$k$}-domination number for strongly chordal graphs [2, 3, 8]. A weak {$k$}-dominating function is a function $g: V(G) \to \{0, \dots, k\}$ such that, for every vertex $x$,

$$g(x) = 0 \quad \text{implies} \quad \sum_{y \in \mathcal{N}(x)} g(y) \geq k. \qquad (2)$$

The weak domination number $\gamma_{wk}(G)$ minimizes $\sum_{x \in V(G)} g(x)$, over all weak {$k$}-dominating functions $g$. In their paper, Chang et al. show that the k-rainbow domination number is polynomial for block graphs. As far as we know, the k-rainbow domination number is open for strongly chordal graphs.

It is easy to see that, for fixed $k$, the k-rainbow domination problem can be formulated in monadic second-order logic. For example, a function $f: V(G) \to 2^k$ can be defined using $k$ vertex subsets $V_1, \dots, V_k$, such that $f(x) = \{i \mid x \in V_i\}$, and the property of k-rainbow can be formulated as

$$\exists_{V_0 \subseteq V(G)} \exists_{V_1 \subseteq V(G)} \dots \exists_{V_k \subseteq V(G)} \left[ \left( \forall x \in V(G) \exists_{i \in [k] \cup \{0\}} x \in V_i \right) \wedge \left( \forall i \in [k] V_0 \cap V_i = \emptyset \right) \wedge \left( \forall x \in V_0 \forall i \in [k] N(x) \cap V_i \neq \emptyset \right) \right].$$

The k-rainbow domination number is the minimal value of $\sum_{i=1}^k |V_i|$, where $(V_1, \dots, V_k)$ defines a k-rainbow function. This shows that, when $k$ is fixed, the parameter is computable in linear time for graphs of bounded treewidth or rankwidth [12].

**Theorem 1.** Let $k \in \mathbb{N}$. There exists a linear-time algorithm that computes $\gamma_{rk}(G)$ for graphs of bounded rankwidth.

For example, Theorem 1 implies that, for each $k$, $\gamma_{rk}(G)$ is computable in polynomial time for distance-hereditary graphs, ie, the graphs of rankwidth 1. Also, graphs of bounded outerplanarity have bounded treewidth, which implies bounded rankwidth.

A direct application of the monadic second-order theory involves a constant which is an exponential function of $k$. In the following section we show that, in some cases, this exponential factor can be avoided. Moreover, besides weak {$k$}-domination, another variant, weak {$k$}-L-domination, is also conducted. A
<figure><img src="image_2.png" /><figcaption>Fig. 1. Results on k-rainbow domination over graph classes. Double-lined rectangles indicate the graph classes conducted in this paper. The arrows “→” denote the relation of containment, ie, A → B means A is a superclass of B. A graph is Cameron if it is (Bull, Gem, Co-Gem, C5)-free [6].</figcaption></figure>

formal definition is given later in Section 3. The corresponding parameter, the weak {k}-L-domination number, is denoted by $\gamma_{wkL}(G)$. We note here that this variant was formulated in order to solve the k-rainbow domination problem [7, 8]. In more detail, the results presented in this paper (see Figure 1) consist of

- linear-time algorithms for cographs on $\gamma_{rk}$ and $\gamma_{wk}$, respectively (Section 2).

- a linear-time algorithm for trivially perfect graphs on $\gamma_{wkL}$ (Section 3).

- a polynomial-time algorithm for interval graphs on $\gamma_{r2}$, which is equal to $\gamma_{w2}$ (Section 4).

- The NP-completeness of computing $\gamma_{rk}$ and $\gamma_{wk}$ for splitgraphs (Section 5).

Because of the space limitation, some proofs and related results are omitted. The details are available in the full version [20].

## 2 k-Rainbow domination on cographs

Cographs are the graphs without an induced $P_4$. As a consequence, cographs are completely decomposable by series and parallel operations, that is, joins and unions [15]. In other words, a graph is a cograph if and only if every nontrivial, induced subgraph is disconnected or its complement is disconnected. Cographs have a rooted, binary decomposition tree, called a cotree, with internal nodes labeled as joins and unions [11].

For a graph $G$ and $k \in \mathbb{N}$, let $F(G, k)$ denote the set of k-rainbow functions on $G$. Furthermore, define

$$F^{+}(G, k) = \{ f \in F(G, k) \mid \forall x \in V(G) f(x) \neq \emptyset \}$$

$$\text{and } F^{-}(G, k) = F(G, k) \setminus F^{+}(G, k).$$
**Theorem 2.** There exists a linear-time algorithm to compute the k-rainbow domination number $\gamma_{rk}(G)$ for cographs G and $k \in \mathbb{N}$.

*Proof.* We describe a dynamic programming algorithm to compute the k-rainbow domination number. A minimizing k-rainbow function can be obtained by back-tracking.

Clearly, for a k-rainbow function that has no empty-set label, the minimal cost is the number of vertices. We therefore concentrate on those k-rainbow functions for which some labels are the empty set.

For a cograph H define

$$ 
\begin{aligned}
R^{+}(H) &= \min \{ \|f\|_{H} \mid f \in F^{+}(H, k) \text{ and } f(V(H)) = [k] \}, \\
R^{-}(H) &= \min \{ \|f\|_{H} \mid f \in F^{-}(H, k) \}.
\end{aligned}
$$

Here, we adopt the convention that $R^{-}(H) = \infty$ if $F^{-}(H, k) = \emptyset$.

Notice that

$$ R^{+}(H) = \max \{ |V(H)|, k \}. \qquad (3) $$

Assume that H is the union of two smaller cographs $H_1$ and $H_2$. Then clearly,

$$ R^{-}(H) = \min \{ R^{-}(H_1) + |V(H_2)|, R^{-}(H_2) + |V(H_1)|, R^{-}(H_1) + R^{-}(H_2) \}. \qquad (4) $$

Now assume that H is the join of two smaller cographs, $H_1$ and $H_2$. We claim

$$ R^{-}(H) = \min \{ R^{+}(H_1), R^{+}(H_2), R^{-}(H_1), R^{-}(H_2), 2k \}. \qquad (5) $$

To show that Equation (5) holds, let f be a k-rainbow function from $F^{-}(H, k)$ with minimum cost over H. First, one can observe that

$$ \|f\|_{H} \le 2k \qquad (6) $$

since in each of $H_1$ and $H_2$, labeling exactly one vertex with $[k]$ and the others with $\emptyset$ results in a k-rainbow function of cost $2k$.

If there exists $i$ in $\{1, 2\}$ such that $f(x) \neq \emptyset$ for all $x \in V(H_i)$, then there is a vertex labeled with $\emptyset$ in $H_{3-i}$. Let $L = \cup_{y \in V(H_{3-i})} f(y)$. Define another k-rainbow function $f'$ of H as follows. Choosing an arbitrary vertex $x$ in $V(H_i)$, let $f'(x) = f(x) \cup L$. For $y \in V(H_i) \setminus \{x\}$, let $f'(y) = f(y)$, and for $z \in V(H_{3-i})$, let $f'(z) = \emptyset$. Notice that $f'(V(H_i)) = [k]$, and thus, $f'$ is a k-rainbow function with cost at most $\|f\|_{H}$. This shows that $R^{-}(H) = R^{+}(H_i)$.

If each of $H_1$ and $H_2$ contains a vertex with label $\emptyset$, let

$$ L_1 = f(V(H_1)) \quad \text{and} \quad L_2 = f(V(H_2)). $$

For each color $\ell \in [k]$, let $\nu_{\ell}$ be the number of times that $\ell$ is used in a label, that is,

$$ \nu_{\ell} = |\{ x \mid x \in V(H) \text{ and } \ell \in f(x) \}|. $$
If for all $\ell$, $\nu_\ell \ge 2$. It follows that $\|f\|_H \ge 2k$. Together with inequality (6), we have $R^-(H) = 2k$. Otherwise, there exists some $\ell$ with $\nu_\ell = 1$. Let $u$ be the unique vertex with $\ell \in f(u)$. Assume that $u \in V(H_1)$. The case where $u \in V(H_2)$ is similar. Clearly, $u$ is adjacent to all $x \in V(H)$ with $f(x) = \emptyset$. Modify $f$ to $f'$ so that $f'(u) = f(u) \cup (L_2 \setminus L_1)$, $f'(x) = f(x)$ for all $x \in V(H_1) \setminus \{u\}$, and $f'(y) = \emptyset$ for all $y \in V(H_2)$. It is not difficult to verify that $f'$ is a $k$-rainbow function from $F^-(H, k)$ with cost at most $\|f\|$. Moreover, $f'$ restricted to $H_1$ is a $k$-rainbow function with minimum cost over $H_1$. Thus, in this case, $R^-(H) = R^-(H_1)$.

At the root of the cotree, we obtain $\gamma_{rk}(G)$ via

$$ \gamma_{rk}(G) = \min \{ |V(G)|, R^-(G) \}. $$

The cotree can be obtained in linear time (see, eg, [5, 10, 18]). Each $R^+(H)$ is obtained in $O(1)$ time via Equation (3), and $R^-(H)$ is obtained in $O(1)$ time via Equations (4) and (5).

This proves the theorem.

□

The weak $\{k\}$-domination number (recall the definition near Equation (2)) was introduced by Brešar, Henning and Rall in [3] as an accessible, ‘monochromatic version’ of $k$-rainbow domination. In the following theorem we turn the tables.

In general, for graphs $G$ one has that $\gamma_{wk}(G) \le \gamma_{rk}(G)$ since, given a $k$-rainbow function $f$ one obtains a weak $\{k\}$-dominating function $g$ by defining, for $x \in V(G)$, $g(x) = |f(x)|$. The parameters $\gamma_{wk}$ and $\gamma_{rk}$ do not always coincide. For example $\gamma_{w2}(C_6) = 3$ and $\gamma_{r2}(C_6) = 4$. Brešar et al. ask, in their Question 3, for which graphs the equality $\gamma_{w2}(G) = \gamma_{r2}(G)$ holds. As far as we know this problem is still open. Chang et al. showed that weak $\{k\}$-domination and $k$-rainbow domination are equivalent for strongly chordal graphs [8].

For cographs equality does not hold. For example,

$$ \text{when } G = (P_3 \oplus P_3) \otimes (P_3 \oplus P_3) \text{ then } \gamma_{w3}(G) = 4 \text{ and } \gamma_{r3}(G) = 6. $$

Let $G$ be a graph and let $k \in \mathbb{N}$. For a function $g: V(G) \to \{0, \dots, k\}$ we write $\|g\|_G = \sum_{x \in V(G)} g(x)$. Furthermore, for $S \subset V(G)$ we write $g(S) = \sum_{x \in S} g(x)$.

**Theorem 3.** There exists an $O(k^2 \cdot n)$ algorithm to compute the weak $\{k\}$-domination number for cographs when a cotree is a part of the input.

*Proof.* Let $k \in \mathbb{N}$. For a cograph $H$ and $q \in \mathbb{N} \cup \{0\}$, define

$$ W(H, q) = \min \{ \|g\|_H \mid g: V(H) \to \{0, \dots, k\} \text{ and } \forall_{x \in V(G)} g(x) = 0 \Rightarrow g(N(x)) + q \ge k \}. $$
When a cograph $H$ is the union of two smaller cographs $H_1$ and $H_2$ then

$$ \gamma_{wk}(H) = \gamma_{wk}(H_1) + \gamma_{wk}(H_2). $$

In such a case, we have

$$ W(H, q) = W(H_1, q) + W(H_2, q). $$

When a cograph $H$ is the join of two cographs $H_1$ and $H_2$ then the minimal cost of a weak $\{k\}$-dominating function is bounded from above by $2k$. Then

$$ W(H, q) = \min \{ W_1+W_2 \mid W_1 = W(H_1, q+W_2) \text{ and } W_2 = W(H_2, q+W_1) \}. $$

The weak $\{k\}$-domination number of a cograph $G$, $W(G, 0)$, can be obtained via the above recursion, spending $O(k^2)$ time in each of the $n$ nodes in the cotree. This completes the proof. □

*Remark 1.* Similar results can be obtained for, eg, the $\{k\}$-domination number [13] and the $(j, k)$-domination number [26, 27].

*Remark 2.* A frequently studied generalization of cographs is the class of $P_4$-sparse graphs. A graph is $P_4$-sparse if every set of 5 vertices induces at most one $P_4$ [19, 22]. We show in the full version that the rainbow domination problem can be solved in linear time on $P_4$-sparse graphs.

### 3 Weak $\{k\}$-L-domination on trivially perfect graphs

Chang et al. were able to solve the $k$-rainbow domination problem (and the weak $\{k\}$-domination problem) for two subclasses of strongly chordal graphs, namely for trees and for blockgraphs. In order to obtain linear-time algorithms, they introduced a variant, called the weak $\{k\}$-L-domination problem [7, 8]. In this section we show that this problem can be solved in $O(k \cdot n)$ time for trivially perfect graphs.

**Definition 2.** A $\{k\}$-assignment of a graph $G$ is a map $L$ from $V(G)$ to ordered pairs of elements from $\{0, \dots, k\}$. Each vertex $x$ is assigned a label $L(x) = (a_x, b_x)$, where $a_x$ and $b_x$ are elements of $\{0, \dots, k\}$. A weak $\{k\}$-L-dominating function is a function $w: V(G) \to \{0, \dots, k\}$ such that, for each vertex $x$ the following two conditions hold.

$$ \begin{array}{l} w(x) \geq a_x, \quad \text{and} \\ w(x) = 0 \quad \Rightarrow \quad w(N[x]) \geq b_x. \end{array} $$

The weak $\{k\}$-L-domination number is defined as

$$ \gamma_{wkL}(G) = \min \{ \|g\| \mid g \text{ is a weak } \{k\}\text{-L-dominating function on } G \}. $$
Notice that

$$ \forall_{x \in V(G)} L(x) = (0, k) \Rightarrow \gamma_{wk}(G) = \gamma_{wkL}(G). $$

**Definition 3.** A graph is trivially perfect if it has no induced $P_4$ or $C_4$.

Wolk investigated the trivially perfect graphs as the comparability graphs of forests. Each component of a trivially perfect graph $G$ has a model which is a rooted tree $T$ with vertex set $V(G)$. Two vertices of $G$ are adjacent if, in $T$, one lies on the path to the root of the other one. Thus each path from a leaf to the root is a maximal clique in $G$ and these are all the maximal cliques. See [9, 17] for the recognition of these graphs. In the following we assume that a rooted tree $T$ as a model for the graph is a part of the (connected) input.

We simplify the problem by using two basic observations. (See [8, 7] for similar observations.) Let $T$ be a rooted tree which is the model for a connected trivially perfect graph $G$. Let $R$ be the root of $T$; note that this is a universal vertex in $G$. We assume that $G$ is equipped with a $\{k\}$-assignment $L$, which attributes each vertex $x$ with a pair $(a_x, b_x)$ of numbers from $\{0, \dots, k\}$.

(I) There exists a weak $\{k\}$-L-dominating function $g$ of minimal cost such that

$$ \forall_{x \in V(G) \setminus \{R\}} a_x > 0 \Rightarrow g(x) = a_x. $$

(II) There exists a weak $\{k\}$-L-dominating function $g$ of minimal cost such that

$$ \forall_{x \in V(G) \setminus \{R\}} a_x = 0 \quad \text{and} \quad b_x \le \sum_{y \in N[x]} a_y \quad \Rightarrow \quad g(x) = 0. $$

**Definition 4.** The reduced instance of the weak $\{k\}$-L-domination problem is the subtree $T'$ of $T$ with vertex set $V(G') \setminus W$, where

$$ W = \{ x \mid x \in V(G) \setminus \{R\} \text{ and } a_x > 0 \} \cup \{ x \mid x \in V(G) \setminus \{R\} \text{ and } a_x = 0 \text{ and } \sum_{y \in N[x]} a_y \ge b_x \}. $$

The labels of the reduced instance are, for $x \ne R$, $L(x) = (a'_x, b'_x)$, where

$$ a'_x = 0 \quad \text{and} \quad b'_x = b_x - \sum_{y \in N[x]} a_y, $$

and the root $R$ has a label $L(R) = (a'_R, b'_R)$, where

$$ a'_R = a_R \quad \text{and} \quad b'_R = \max \{ 0, b - \sum_{x \in V(G) \setminus \{R\}} a_x \}. $$
The previous observations prove the following lemma.

**Lemma 1.** Let $T'$ and $L'$ be a reduced instance of a weak $\{k\}$-L-domination problem. Then

$$ \gamma_{wkL}(G) = \gamma_{wkL'}(G') + \sum_{x \in V(G) \setminus \{R\}} a_x. $$

In the following, let $G$ be a connected, trivially perfect graph and let $G$ be equipped with a $\{k\}$-assignment. Let $G' = (V', E')$ be a reduced instance with model a $T'$ and a root $R$, and a reduced assignment $L'$. Let $g$ be a weak $\{k\}$-L'-dominating function on $G'$ of minimal cost. Notice that we may assume that

$$ \forall_{x \in V(G') \setminus \{R\}} g(x) \in \{0, 1\}. $$

Let $x$ be an internal vertex in the tree $T'$ and let $Z$ be the set of descendants of $x$. Let $P$ be the path in $T'$ from $x$ to the root $R$. Assume that $Z$ is a union of $r$ distinct cliques, say $B_1, \dots, B_r$. Assume that the vertices of each $B_j$ are ordered $x_1^j, \dots, x_{r_j}^j$ such that

$$ p \le q \Rightarrow b'_{x_p^j} \ge b'_{x_q^j}. $$

Define $d_{x_p^j} = b'_{x_p^j} - p + 1$. Relabel the vertices of $Z$ as $z_1, \dots, z_\ell$ such that

$$ p \le q \Rightarrow d_{z_p} \ge d_{z_q}. $$

**Lemma 2.** There exists an optimal weak $\{k\}$-L'-dominating function $g$ such that $g(z_i) \ge g(z_j)$ when $i < j$.

We refer to [20] for further details.

**Definition 5.** For $a \in \{0, \dots, k\}$, $a \ge a'_R$, let $\Gamma(G', L', a)$ be the minimal cost over all weak $\{k\}$-L'-dominating functions $g$ on $G'$ on condition that $g(P) \ge a$.

**Lemma 3.** Define $d_{z_{\ell+1}} = a$. Let $i^* \in \{1, \dots, \ell+1\}$ be such that

(a) $\max \{a, d_{z_i^*}\} + i^* - 1$ is smallest possible, and

(b) $i^*$ is smallest possible with respect to (a).

Let $H = G' - Z$. Let $L^H$ be the restriction of $L'$ to $V(H)$ with the following modifications.

$$ \forall_{y \in P} b_y^H = \max \{0, b_y' - i^* + 1\}. $$

Let $a^H = \max \{a, d_{z_{i^*}}\}$. Then

$$ \Gamma(G', L', a) = \Gamma(H, L^H, a^H) + i^* - 1. $$
We refer to [20] for further details.

The previous lemmas prove the following theorem.

**Theorem 4.** Let G be a trivially perfect graph with n vertices. Let T be a rooted tree that represents G. Let $k \in \mathbb{N}$ and let L be a $\{k\}$-assignment of G. Then there exists an $O(k \cdot n)$ algorithm that computes a weak $\{k\}$-L-dominating function of G.

The related $(j, k)$-domination problem can be solved in linear time on trivially perfect graphs. The weak $\{k\}$-L-domination problem can be solved in linear time on complete bipartite graphs. A detailed discussion can be found in the full version [20].

# 4 2-Rainbow domination of interval graphs

In [3] the authors ask four questions, the last one of which is, whether there is a polynomial algorithm for the 2-rainbow domination problem on (proper) interval graphs. In this section we show that 2-rainbow domination can be solved in polynomial time on interval graphs.

We use the equivalence of the 2-rainbow domination problem with the weak $\{2\}$-domination problem. The equivalence of the two problems, when restricted to trees and interval graphs, was observed in [3]. Chang et al., proved that it holds for general k when restricted to the class of strongly chordal graphs [8]. The class of interval graphs is properly contained in that of the strongly chordal graphs.

An interval graph has a consecutive clique arrangement. That is a linear ordering $[C_1, \dots, C_t]$ of the maximal cliques of the interval graph such that, for each vertex, the cliques that contain it occur consecutively in the ordering [16].

Bršar and Šumenjak proved the following theorem.

**Theorem 5 (See [3]).** When G is an interval graph,

$$ \gamma_{w2}(G) = \gamma_{r2}(G). $$

In the following, let $G = (V, E)$ be an interval graph.

**Lemma 4.** There exists a weak $\{2\}$-dominating function g, with $g(V) = \gamma_{r2}(G)$, such that every maximal clique has at most 2 vertices assigned the value 2.

*Proof.* Assume that $C_i$ is a maximal clique in the consecutive clique arrangement of G. Assume that $C_i$ has 3 vertices x, y and z with $g(x) = g(y) = g(z) = 2$. Assume that, among the three of them, x has the most neighbors in $\cup_{j \ge i} C_j$ and that y has the most neighbors in $\cup_{j \le i} C_j$. Then any neighbor of z is also a neighbor of x or it is a neighbor of y. So, if we redefine $g(z) = 1$, we obtain a weak $\{2\}$-dominating function with value less than $g(V)$, a contradiction. □
**Lemma 5.** There exists a weak {2}-dominating function g with minimum value $g(V) = \gamma_{r2}(G)$ such that every maximal clique has at most four vertices with value 1.

*Proof.* The proof is similar to that of Lemma 4. Let $C_i$ be a clique in the consecutive clique arrangement of $G$. Assume that $C_i$ has 5 vertices $x_i$, $i \in \{1, \dots, 5\}$, with $g(x_i) = 1$ for each $i$. Order the vertices $x_i$ according to their neighborhoods in $\cup_{j \ge i} C_j$ and according to their neighborhoods in $\cup_{j \le i} C_j$. For simplicity, assume that $x_1$ and $x_2$ have the most neighborhoods in the first union of cliques and that $x_3$ and $x_4$ have the most neighbors in the second union of cliques. Then $g(x_5)$ can be reduced to zero; any other vertex that has $x_5$ in its neighborhood already has two other 1's in it.

This proves the lemma. □

**Theorem 6.** There exists a polynomial algorithm to compute the 2-rainbow domination number for interval graphs.

The proof of this theorem and some remarks are moved to the full version [20].

We obtained similar results for the class of permutation graphs. We refer to the full version [20] for the details.

# 5 NP-Completeness for splitgraphs

A graph $G$ is a splitgraph if $G$ and $\tilde{G}$ are both chordal. A splitgraph has a partition of its vertices into two sets $C$ and $I$, such that the subgraph induced by $C$ is a clique and the subgraph induced by $I$ is an independent set.

Although the NP-completeness of k-rainbow domination for chordal graphs was established in [7], their proof does not imply the intractability for the class of splitgraphs. However, that is easy to mend.

**Theorem 7.** For each $k \in \mathbb{N}$, the k-rainbow domination problem is NP-complete for splitgraphs.

*Proof.* Since domination is NP-complete for splitgraphs [4], this proves that k-rainbow domination is NP-complete for $k = 1$. For $k \ge 2$, assume that $G$ is a splitgraph with maximal clique $C$ and independent set $I$. Construct an auxiliary graph $G'$ by making $k-1$ pendant vertices adjacent to each vertex of $C$. Thus $G'$ has $|V(G)| + |C|(k-1)$ vertices, and $G'$ remains a splitgraph. We prove that

$$ \gamma_{rk}(G') = \gamma(G) + |C| \cdot (k-1). $$

We first show that

$$ \gamma_{rk}(G') \le \gamma(G) + |C| \cdot (k-1). $$

Consider a dominating set $D$ of $G$ with $|D| = \gamma(G)$. We use $D$ to construct a k-rainbow function $f$ for $G'$ as follows:
- For any $v \in D$, if $v \in C$, let $f(v) = [k]$; else, if $v \in I$, let $f(v) = \{k\}$;

- For any $v \in V(G) \setminus D$, let $f(v) = \emptyset$;

- For the $k-1$ pendant vertices attaching to a vertex $v \in C$, if $f(v) = [k]$, then $f$ assigns to each of these pendant vertices an empty set. Otherwise, if $f(v) = \emptyset$, then $f$ assigns the distinct size-1 sets $\{1\}, \{2\}, \dots, \{k-1\}$ to these pendant vertices, respectively.

It is straightforward to check that $f$ is a $k$-rainbow function. Moreover, we have

$$ \gamma_{rk}(G') \leq \sum_{x \in V(G')} |f(x)| = \gamma(G) + |C| \cdot (k-1). $$

We now show that

$$ \gamma_{rk}(G') \geq \gamma(G) + |C| \cdot (k-1). $$

Consider a minimizing $k$-rainbow function $f$ for $G'$. Without loss of generality, we further assume that $f$ assigns either $\emptyset$ or a size-1 subset to each pendant vertex.<fnref n="4" /> Define $D \subseteq V(G)$ as

$$ D = \{ x \mid f(x) \neq \emptyset \text{ and } x \in V(G) \}. $$

That is, $D$ is formed by removing all the pendant vertices in $G'$, and selecting all those vertices where $f$ assigns a non-empty set. Observe that $D$ is a dominating set of $G$.<fnref n="5" /> Moreover, we have

$$ \begin{aligned} |D| &= \sum_{x \in C} [f(x) \neq \emptyset] + \sum_{x \in I} [f(x) \neq \emptyset] \\ &\leq \sum_{x \in V(G') \setminus I} |f(x)| - |C| \cdot (k-1) + \sum_{x \in I} |f(x)| \\ &\leq \sum_{x \in V(G')} |f(x)| - |C| \cdot (k-1), \end{aligned} $$

where the first inequality follows from the fact that for each $v \in C$ and its corresponding pendant vertices $P_v$,

$$ |f(v)| + \sum_{x \in P_v} |f(x)| - (k-1) = \begin{cases} 0 & \text{if } f(v) = \emptyset \\ \geq 1 & \text{if } f(v) \neq \emptyset. \end{cases} $$

<footnote n="4">⁴ Otherwise, if a pendant vertex $p$ attaching $v$ is assigned a set with two or more labels, say $f(p) = \{\ell_1, \ell_2, \dots\}$, we modify $f$ into $f'$ so that $f'(p) = \{\ell_1\}$, $f'(v) = f(v) \cup (f(p) \setminus \{\ell_1\})$, and $f'(x) = f(x)$ for the remaining vertices; the resulting $f'$ is still a minimizing $k$-rainbow function.</footnote>

<footnote n="5">⁵ That is so because for any $v \in V(G) \setminus D$, we have $f(v) = \emptyset$ so that the union of labels of $v$'s neighbor in $G'$ is $[k]$; however, at most $k-1$ neighbors of $v$ are removed, and each was assigned a size-1 set, so that $v$ must have at least one neighbor in $D$.</footnote>
Consequently, we have

$$ \gamma(G) \leq |D| \leq \gamma_{rk}(G') - |C| \cdot (k-1). $$

This proves the theorem.

□

Similarly, we have the following theorem.

**Theorem 8.** For each $k \in \mathbb{N}$, the weak $\{k\}$-domination problem is NP-complete for splitgraphs.

*Proof.* Let $G$ be a splitgraph with maximal clique $C$ and independent set $I$. Construct the graph $G'$ as in Theorem 7, by adding $k-1$ pendant vertices to each vertex of the maximal clique $C$. We prove that

$$ \gamma_{wk}(G') = \gamma(G) + |C| \cdot (k-1). $$

First, let us prove that

$$ \gamma_{wk}(G') \leq \gamma(G) + |C|(k-1). $$

Let $D$ be a minimum dominating set. Construct a weak $\{k\}$-domination function $g: V(G') \to \{0, \dots, k\}$ as follows.

(i) For $x \in D \cap C$, let $g(x) = k$.

(ii) For $x \in D \cap I$, let $g(x) = 1$.

(iii) For $x \in V(G) \setminus D$, let $g(x) = 0$.

(iv) For a pendant vertex $x$ with $N(x) \in D$, let $g(x) = 0$.

(v) For a pendant vertex $x$ with $N(x) \notin D$, let $g(x) = 1$.

It is easy to check that $g$ is a weak $\{k\}$-dominating function with cost

$$ \gamma_{wk}(G') \leq \sum_{x \in V(G')} g(x) = \gamma(G) + |C| \cdot (k-1). $$

To prove the converse, let $g$ be a weak $\{k\}$-dominating function for $G'$ of minimal cost. We may assume that $g(x) \in \{0, 1\}$ for every pendant vertex $x$. Define

$$ D = \{ x \mid x \in V(G) \text{ and } g(x) > 0 \}. $$

Then $D$ is a dominating set of $G$. Furthermore,

$$ \begin{aligned} \gamma(G) \leq |D| &= \sum_{x \in C} [g(x) > 0] + \sum_{x \in I} [g(x) > 0] \\ &\leq \sum_{x \in V(G') \setminus I} g(x) - |C| \cdot (k-1) + \sum_{x \in I} g(x) \\ &\leq \sum_{x \in V(G')} g(x) - |C| \cdot (k-1) \\ &\leq \gamma_{wk}(G') - |C| \cdot (k-1). \end{aligned} $$

This proves the theorem.

□
**Acknowledgments** The authors would like to thank the anonymous reviewers for helpful comments. Wing-Kai Hon and Hsiang-Hsuan Liu were supported in part by MOST grant 102-2221-E-007-068. Hung-Lung Wang was supported in part by MOST grant 103-2221-E-141-004. Both grants are from the Ministry of Science and Technology, Taiwan.

References

1. Aharoni, R. and T. Szabó, Vizing's conjecture for chordal graphs, *Discrete Mathematics* **309** (2009), pp. 1766-1768.

2. Brešar, B., M. Henning and D. Rall, Rainbow domination in graphs, *Taiwanese Journal of Mathematics* **12** (2008), pp. 213–225.

3. Brešar, B., T. Šumenjak, On 2-rainbow domination in graphs, *Discrete Applied Mathematics* **155** (2007), pp. 2394–2400.

4. Bertossi, A., Dominating sets for split and bipartite graphs, *Information Processing Letters* **19** (1984), pp. 37–40.

5. Bretscher, A., D. Corneil, M. Habib and C. Paul, A simple linear time LexBFS cograph recognition algorithm, *SIAM Journal on Discrete Mathematics* **22** (2008), pp. 1277–1296.

6. Cameron, P., Two-graphs and trees, *Discrete Mathematics* **127** (1994), pp. 63–74.

7. Chang G., J. Wu and X. Zhu, Rainbow domination on trees, *Discrete Applied Mathematics* **158** (2010), pp. 8–12.

8. Chang, G., B. Li and J. Wu, Rainbow domination and related problems on strongly chordal graphs, *Discrete Applied Mathematics* **161** (2013), pp. 1395–1401.

9. Chu, F., A simple linear time certifying LBFS-based algorithm for recognizing trivially perfect graphs and their complements, *Information Processing Letters* **107** (2008), pp. 7–12.

10. Corneil, D., H. Lerchs and L. Stewart-Burlingham, Complement reducible graphs, *Discrete Applied Mathematics* **3** (1981), pp. 163–174.

11. Corneil, D., Y. Perl and L. Stewart, A linear recognition algorithm for cographs, *SIAM Journal on Computing* **14** (1985), pp. 926–934.

12. Courcelle, B., The expression of graph properties and graph transformations in monadic second-order logic. In: *handbook of graph grammars and graph transformations*, World Scientific Publishing Co., Inc. River Edge, NJ, USA, 1997.

13. Domke, G., S. Hedetniemi, R. Laskar and G. Fricke, Relationships between integer and fractional parameters of graphs. In (Y. Alavi, G. Chartrand, O. Oellermann and A. Schwenk eds.) Graph theory, combinatorics, and applications, *Proceedings of the 6th quadrennial international conference on the theory and applications of graphs* **1** (Kalamzaoo, MI 1988), pp. 371–387, Wiley, 1991.

14. Farber, M., Domination, independent domination, and duality in strongly chordal graphs, *Discrete Applied Mathematics* **7** (1984), pp. 115–130.

15. Gallai, T., Transitiv orientierbare Graphen, *Acta Math. Acad. Sci. Hung.* **18** (1967), pp. 25–66.
A translation appears in (J. Ramírez-Alfonsín and B. Reed, eds) *Perfect graphs*,
John Wiley & Sons, Interscience series in discrete mathematics and optimization,
Chichester, 2001.

16. Gilmore, P. and A. Hoffman, A characterization of comparability graphs and of interval graphs, *Canadian Journal of Mathematics* **16** (1964), pp. 539–548.
17. Golumbic, M., Trivially perfect graphs, *Discrete Mathematics* **24** (1978), pp. 105–107.

18. Habib, M. and C. Paul, A simple linear time algorithm for cograph recognition, *Discrete Applied Mathematics* **145** (2005), pp. 183–197.

19. Hoàng, C., *A class of perfect graphs*, Master's thesis, School of Computer Science, McGill University, Montreal, 1983.

20. Hon, W.-K., T. Kloks, H.-H. Liu and H.-L. Wang, Rainbow domination and related problems on some classes of perfect graphs, arXiv:1502.07492 [cs.DM], 2015.

21. Hartnell, B. and D. Rall, On dominating the Cartesian product of a graph and $K_2$, *Discussiones Mathematicae Graph Theory* **24** (2004), pp. 389–402.

22. Jamison, B. and S. Olariu, A tree representation for $P_4$-sparse graphs, *Discrete Applied Mathematics* **35** (1992), pp. 115–129.

23. Pai, K. and W. Chiu, 3-Rainbow domination number in graphs, *Proceedings of the Institute of Industrial Engineers Asian Conference 2013*, Springer, Science+Business Media Singapore (2013), pp. 713–720.

24. van Rooij, J., *Exact exponential-time algorithms for domination problems in graphs*, PhD Thesis, Utrecht University, 2011.

25. van Rooij, J. and H. Bodlaender, Exact algorithms for dominating set, *Discrete Applied Mathematics* **159** (2011), pp. 2147–2164.

26. Rubalcaba, R. and P. Slater, Efficient $(j, k)$-domination, *Discussiones Mathematicae Graph Theory* **27** (2007), pp. 409–423.

27. Rubalcaba, R. and P. Slater, A note on obtaining $k$ dominating sets from a $k$-dominating function on a tree, *Bull. Inst. Combin. Appl.* **51** (2007), pp. 47–54.

28. Šumenjak, T., D. Rall and A. Tepeh, Rainbow domination in the lexicographic product of graphs. Manuscript on ArXiv: 1210.0514, 2012.

29. Vizing, V., Some unsolved problems in graph theory, *Uspehi Mat. Naukno.* (in Russian) **23** (1968), pp. 117–134.

30. Yen, C., 2-Rainbow domination and its practical variations on weighted graphs, *Advances in Intelligent Systems and Applications – Vol. 1, Smart Innovation, Systems and Technologies* **20** (2013), pp. 59–68.