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

HAL
open science

# The Algorithmic Complexity of k-Domatic Partition of Graphs

Hongyu Liang

► To cite this version:

Hongyu Liang. The Algorithmic Complexity of k-Domatic Partition of Graphs. 7th International Conference on Theoretical Computer Science (TCS), Sep 2012, Amsterdam, Netherlands. pp.240-249, 10.1007/978-3-642-33475-7_17. hal-01556216

HAL Id: hal-01556216

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

Submitted on 4 Jul 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_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# The Algorithmic Complexity of *k*-Domatic Partition of Graphs*\*

Hongyu Liang

Institute for Interdisciplinary Information Sciences,
Tsinghua University, Beijing, China.
lianghy08@mails.tsinghua.edu.cn

**Abstract.** Let $G = (V, E)$ be a simple undirected graph, and $k$ be a positive integer. A *k*-dominating set of $G$ is a set of vertices $S \subseteq V$ satisfying that every vertex in $V \setminus S$ is adjacent to at least $k$ vertices in $S$. A *k*-domatic partition of $G$ is a partition of $V$ into $k$-dominating sets. The $k$-domatic number of $G$ is the maximum number of $k$-dominating sets contained in a $k$-domatic partition of $G$. In this paper we study the $k$-domatic number from both algorithmic complexity and graph theoretic points of view. We prove that it is $\mathcal{NP}$-complete to decide whether the $k$-domatic number of a bipartite graph is at least 3, and present a polynomial time algorithm that approximates the $k$-domatic number of a graph of order $n$ within a factor of $(\frac{1}{k} + o(1)) \ln n$, generalizing the $(1 + o(1)) \ln n$ approximation for the 1-domatic number given in [5]. In addition, we determine the exact values of the $k$-domatic number of some particular classes of graphs.

## 1 Introduction

In this paper we consider only simple and undirected graphs, and we follow [3] for notations and terminologies in graph theory. Let $G = (V, E)$ be a simple and undirected graph. For a vertex $v \in V$, let $N_G(v)$ denote the set of neighbors of $v$, and $deg_G(v) = |N_G(v)|$ is the degree of $v$. When no ambiguity arises, we sometimes drop the subscript $G$. Let $\delta(G) = \min_{v \in V}\{deg(v)\}$ be the minimum degree of $G$. For an integer $k \ge 1$, a $k$-coloring of $G$ is a mapping $c : V \rightarrow \{1, 2, \dots, k\}$ such that $c(u) \neq c(v)$ whenever $\{u, v\} \in E$. We say $G$ is $k$-colorable if $G$ has a $k$-coloring.

Domination theory is a very important branch of graph theory which has found applications in numerous areas; see [12, 13] for a comprehensive treatment and some detailed surveys on (earlier) results of domination in graphs. A set of vertices $S \subseteq V$ is called a dominating set of $G$ if every vertex in $V \setminus S$ has at least one neighbor in $S$. The domination number of $G$ is the minimum size of a dominating set of $G$. A *domatic partition* of $G$ is a partition of $V$ into

<footnote>\* This work was supported in part by the National Basic Research Program of China Grant 2011CBA00300, 2011CBA00301, and the National Natural Science Foundation of China Grant 61033001, 61061130540, 61073174.</footnote>
(disjoint) dominating sets of $G$. The *domatic number* of $G$, denoted by $d(G)$,
is the maximum number of dominating sets in a *domatic partition* of $G$. The
concept of *domatic number* was introduced by Cockayne and Hedetniemi [2],
which has been proven very useful in various situations such as locating facilities
in a network [9], clusterhead rotation in sensor networks [17], prolonging the
lifetime and conserving energy of networks [14, 18], and many others.

Let $k \ge 1$ be a fixed integer. A $k$-dominating set of $G$ is a set of vertices $S \subseteq V$
with the property that every vertex in $V \setminus S$ has at least $k$ neighbors in $S$. Clearly
a 1-dominating set is just a dominating set. The notion of $k$-dominating set was
proposed by Fink and Jacobson [6, 7], and has since then been extensively studied
for both its theoretical interest and its practical applications in fault-tolerant
domination in networks; see, e.g., [1, 4, 8, 19, 20] and the references therein. It
is known that deciding the size of the minimum $k$-dominating set of a graph is
NP-hard [21]. (In the literature, some researchers use the name $k$-dominating set
to refer to another variant of dominating set, namely the distance-$k$ dominating
set [11, 16].)

A $k$-domatic partition of $G$ is a partition of $V$ into (disjoint) $k$-dominating sets of $G$. The $k$-domatic number of $G$, denoted by $d_k(G)$, is the maximum number of $k$-dominating sets in a $k$-domatic partition of $G$. Thus $d_1(G) = d(G)$. The concept of $k$-domatic number was first studied by Zelinka [22] under the name “$k$-ply domatic number,” and was later rediscovered and studied under its current name by Kämmerling and Volkmann [15]. This concept is useful for modeling networks that need domatic partitions with higher degree of domination. As an example, imagine that we wish to locate resources in a network to facilitate the users (i.e., nodes). A user in the network can access resources only from itself and his neighboring nodes. A user is surely happy if there is one resource at his location, but if not, he would only be satisfied if he could access at least $k$ copies of resources from its neighbors, keeping the possibility of multiple choices as a compensation of distance. Then the set of nodes with resources satisfying all the users is exactly a $k$-dominating set of the network. Now suppose we wish to distribute different types of resources (to enhance the quality of life of users) with the natural constraint that at most one kind of resource can be placed at each node. Then the maximum number of resource types that can be put in the network is precisely the $k$-domatic number of its underlying graph.

Despite being a natural generalization of the domatic number whose combi-
natorial and algorithmic aspects have both been well understood, the *k*-domatic
number lacks an investigation from a complexity viewpoint, which motivates our
study.

In this paper, we explore the *k*-domatic number mainly from the algorithmic
complexity point of view, and obtain several results that fill the blank in this
line of research. In Section 2 we prove that for every *k* ≥ 1, it is *NP*-complete
to decide whether the *k*-domatic number of a given bipartite graph is at least 3.
This generalizes the NP-completeness result for the 1-domatic number [10]. We
then present in Section 3 a polynomial time algorithm that approximates the
*k*-domatic number of a given graph of order *n* within factor ($\frac{1}{k} + o(1)$) $\ln n$, which
generalizes the $(1 + o(1)) \ln n$ approximation for the domatic number given in [5]. Finally, as a minor contribution, we determine in Section 4 the exact values of the *k*-domatic number of some special classes of graphs.

## 2 Complexity of Computing the *k*-Domatic Number

In this section we show the hardness of computing the *k*-domatic number of a graph. Our main theorem is as follows.

**Theorem 1.** For every fixed integer $k \ge 1$, it is $\mathcal{NP}$-complete to decide whether the *k*-domatic number of a given graph is at least 3.

To establish Theorem 1 we introduce a new variant of the coloring problem, which may have its own interest in other scenarios. Let $k$ be a fixed positive integer and $H = (V, E)$ be a $2k$-uniform hypergraph, i.e., a hypergraph in which each edge contains exactly $2k$ vertices. A mapping $c: V \to \{1, 2, 3\}$ is called a balanced $3$-coloring of $H$ if for every $e \in E$, there exist $1 \le i < j \le 3$ such that $|c^{-1}(i) \cap e| = |c^{-1}(j) \cap e| = k$; that is, every edge of $H$ contains exactly $k$ vertices of color $i$ and $k$ vertices of color $j$ (and no vertices of the color other than $i$ and $j$). Define the $2k$-UNIFORM HYPERGRAPH BALANCED 3-COLORING PROBLEM as follows:

$2k$-UNIFORM HYPERGRAPH BALANCED 3-COLORING PROBLEM ($2k$HB3C, for short)

*Instance:* A $2k$-uniform hypergraph $H$.

*Question:* Does $H$ have a balanced $3$-coloring?

**Lemma 1.** For every fixed integer $k \ge 1$, $2k$HB3C is $\mathcal{NP}$-complete.

*Proof.* Let $k$ be a fixed positive integer. The $2k$HB3C problem is clearly in $\mathcal{NP}$, since we can verify in polynomial time whether a given mapping is a balanced $3$-coloring of $H$ by exhaustively checking all its edges. We now present a polynomial-time reduction from the GRAPH 3-COLORING problem (G3C for short), which is a classical $\mathcal{NP}$-complete problem [10], to $2k$HB3C. An instance of G3C consists of a graph $G$, and the goal is to decide whether $G$ is $3$-colorable. Let $G = (V, E)$ be a graph serving as the input to G3C. We will construct a $2k$-uniform hypergraph $H$ from $G$. Informally speaking, the hypergraph $H$ can be obtained as follows: For each edge $e \in E$, we associate it with a $2k$-uniform hypergraph $H_e$, where $H_e$ has vertex set $X_e \cup Y_e$ with $|X_e| = |Y_e| = 3k$, and contains all possible hyperedges that consist of exactly $k$ vertices from $X_e$ and another $k$ vertices from $Y_e$. The number of such hyperedges is $\binom{3k}{k} \cdot \binom{3k}{k} < 2^{6k}$, which is a constant since $k$ is a fixed integer. Let $H$ be the union of all such (disjoint) hypergraphs. Finally, for each $e \in E$, add to $H$ a hyperedge which consists of both vertices in $e$, the first $k-1$ vertices in $X_e$, and the first $k-1$ vertices in $Y_e$. This finishes the construction of $H$. It is clear that $H$ can be constructed in polynomial time.

We now give a rigorous definition of $H$. For every $e \in E$, let
- $X_e = \{x_{e,i} | 1 \le i \le 3k\}$ and $Y_e = \{y_{e,i} | 1 \le i \le 3k\}$;

- $E'_e = \{X \cup Y | X \subseteq X_e; Y \subseteq Y_e; |X| = |Y| = k\}$;

- $e' = e \cup \{x_{e,i}, y_{e,i} | 1 \le i \le k-1\}$.

Let $V' = V \cup \bigcup_{e \in E} (X_e \cup Y_e)$, and $E' = \{e' | e \in E\} \cup \bigcup_{e \in E} E'_e$. Finally let $H = (V', E')$. It is easy to verify that $H$ is a 2k-uniform hypergraph with $|V'| = |V| + 6k|E|$ and $|E'| = (1 + \binom{3k}{k}) \cdot \binom{3k}{k})|E|$.

We will prove that $G$ is 3-colorable if and only if $H$ has a balanced 3-coloring.

First consider the “only if” direction. Assume that $G$ is 3-colorable and $c: V \to \{1,2,3\}$ is a 3-coloring of $G$. Define a function $c': V' \to \{1,2,3\}$ as follows. First let $c'(v) = c(v)$ for all $v \in V$. For each edge $e = \{u,v\} \in E$, suppose $c(u) = a$ and $c(v) = b$ where $a, b \in \{1,2,3\}$ (note that $a \neq b$). Then, let $c'(x) = a$ for all $x \in X_e$ and $c'(y) = b$ for all $y \in Y_e$. We verify that the mapping $c'$ defined above is a balanced 3-coloring of $H$. This can be seen as follows:

- For each hyperedge $h = X \cup Y$ with $X \subseteq X_e$ and $Y \subseteq Y_e$ for some $e \in E$, by our definition, $h$ contains exactly $k$ vertices of the same color with that of one endpoint of $e$, and another $k$ vertices of the same color with that of the other endpoint of $e$. Since the two endpoints of $e$ have different colors, $h$ satisfies the property of balanced 3-coloring.

- For each hyperedge $e' = e \cup \{x_{e,i}, y_{e,i} | 1 \le i \le k-1\}$ for some $e$, similar to the previous case, $h$ consists of precisely $k$ vertices of one color and the other $k$ vertices of another color.

Therefore, $c'$ is a balanced 3-coloring of $H$.

We next consider the “if” direction. Suppose that $c'$ is a balanced 3-coloring of $H$. Let $e = \{u,v\}$ be an arbitrary edge in $E$. We claim that all the vertices in $X_e$ have the same color $i$ for some $i \in \{1,2,3\}$, all those in $Y_e$ have the same color $j$ for some $j \in \{1,2,3\}$, and $i \neq j$. This will imply that $u$ and $v$ have different colors under $c'$, since otherwise the hyperedge $e' = e \cup \{x_{e,i}, y_{e,i} | 1 \le i \le k-1\}$ is not balanced. We now prove the above claim. As $|X_e| = 3k$, there exists $i \in \{1,2,3\}$ such that the number of vertices in $X_e$ with color $i$ is at least $k$; without loss of generality we assume that $c'(x_{e,1}) = c'(x_{e,2}) = \dots = c'(x_{e,k}) = i$. Since the hyperedge $\{x_{e,1}, x_{e,2}, \dots, x_{e,k}\} \cup Y$ exists for all $Y \subseteq Y_e$ with $|Y| = k$, we know that in every size-$k$ subset of $Y_e$, all the vertices have the same color. Thus, all vertices in $Y_e$ has the same color, say $j$, and obviously $j \neq i$. Analogously, all vertices in $X_e$ has the same color $i$, proving the claim. According to our previous analysis, the claim implies that $c'(u) \neq c'(v)$ for all $\{u,v\} \in E$. Therefore, the mapping $c: V \to \{1,2,3\}$ defined by $c(v) = c'(v)$ for all $v \in V$ is a 3-coloring of $G$, and hence $G$ is 3-colorable.

This finishes the reduction from G3C to $2k$HB3C, and thus concludes the proof of Lemma 1.

We now proceed to prove Theorem 1.

*Proof (of Theorem 1).* Let $k$ be a fixed positive integer. We reduce $2k$HB3C to the problem of deciding whether $d_k(G) \ge 3$ for a given graph $G$. Note that the
latter problem is clearly in $\mathcal{NP}$. Let $H = (V, E)$ be a 2k-uniform hypergraph given as an input to the 2kHB3C problem. We construct a graph $G = (V', E')$ as follows. Let $V' = X \cup Y \cup Z$, where $X = \{x_e \mid e \in E\}$, $Y = \{y_v \mid v \in V\}$, and $Z = \{z_i \mid 1 \le i \le 3k\}$. Let $E' = \{\{x_e, y_v\} \mid v \in e \in E\} \cup \{\{y_v, z_i\} \mid v \in V; 1 \le i \le 3k\} \cup \{\{z_i, z_j\} \mid 1 \le i < j \le 3k\}$. Thus, $G[X \cup Y]$ is the incidence graph of $H$, $G[Y \cup Z]$ contains a complete bipartite subgraph with partition $(Y, Z)$, and $G[Z]$ is a clique. It is clear that the construction of $G$ can be finished in polynomial time.

We shall show that $H$ has a balanced 3-coloring if and only if $d_k(G) \ge 3$, which will complete the reduction and prove the $\mathcal{NP}$-completeness of the desired problem.

First consider the “only if” direction. Assume that $H$ has a balanced 3-coloring $c: V \to \{1, 2, 3\}$. For each $e \in E$ let $C_e = \{i \mid \exists v \in e \text{ s.t. } c(v) = i\}$; clearly $|C_e| = 2$. We now design a partition $(V'_1, V'_2, V'_3)$ of $V'$ as follows: For each $i \in \{1, 2, 3\}$, let $V'_i = \{x_e \mid i \notin C_e\} \cup \{y_v \mid c(v) = i\} \cup \{z_j \mid (i-1)k + 1 \le j \le ik\}$. It is easy to see that this is indeed a partition of $V'$. Furthermore, we will prove that for each $i \in \{1, 2, 3\}$, $V'_i$ is a $k$-dominating set of $G$. Fix $i \in \{1, 2, 3\}$. Notice that $V' \setminus V'_i = \{x_e \mid i \in C_e\} \cup \{y_v \mid c(v) \neq i\} \cup \{z_j \mid j \in \{1, \dots, 3k\} \setminus \{(i-1)k + 1, \dots, ik\}\}$. By our construction of $G$, every vertex in $(Y \cup Z) \setminus V'_i$ is adjacent to $k$ vertices in $V'_i$, which are $z_{(i-1)k+1}, \dots, z_{ik}$. For each $x_e \in X \setminus V'_i$, we have $i \in C_e$ by our definition of $V'_i$. Thus, there exists $u \in e$ for which $c(u) = i$. Because $c$ is a balanced 3-coloring of $H$, there exist exactly $k$ vertices in $e$ that have value $i$ under $c$, which indicates that those $k$ vertices are all included in $V'_i$. Therefore, $x_e$ is adjacent to at least $k$ vertices in $V'_i$. This proves that $V'_i$, for every $i \in \{1, 2, 3\}$, is a $k$-dominating set of $G$, and hence $d_k(G) \ge 3$, finishing the proof of the “only if” direction of the reduction.

We now turn to the “if” direction. Assume that $d_k(G) \ge 3$ and $(V'_1, V'_2, V'_3)$ is a $k$-domatic partition of $G$. Define a mapping $c: V \to \{1, 2, 3\}$ as follows: For every $v \in V$, let $c(v) = i$ where $i$ is the unique integer satisfying that $y_v \in V'_i$. We show that $c$ is a balanced 3-coloring of $H$. Consider an arbitrary edge $e \in E$, and assume without loss of generality that $x_e \in V'_1$ (and thus $x_e \notin V'_2 \cup V'_3$). By the definition of $k$-dominating sets, for each $j \in \{2, 3\}$, $|N_G(x_e) \cap V'_j| \ge k$. As $|N_G(x_e)| = |\{y_v \mid v \in e\}| = 2k$ and $V'_2 \cap V'_3 = \emptyset$, we have $|N_G(x_e) \cap V'_2| = |N_G(x_e) \cap V'_3| = k$. Thus, $c(y_v) = 2$ for exactly $k$ vertices $v \in e$, and $c(y_v) = 3$ for the other $k$ ones, showing the validity of the coloring on edge $e$. Hence, $c$ is indeed a balanced 3-coloring of $H$. This concludes the “if” direction of the reduction.

The proof of Theorem 1 is thus completed.

We remark that the $\mathcal{NP}$-completeness result holds even if the input graph is bipartite. To see this, we modify the construction of $G$ in the proof as follows: Add $3k$ vertices $\{z'_i \mid 1 \le i \le 3k\}$ to $H$, add an edge between every possible pair $(z_i, z'_j)$, and let $H[Z]$ be an empty graph (instead of being a complete graph as in the previous proof). Then it is easy to verify that $G$ is a bipartite graph. The remaining part of the proof goes through analogously. The only modification is that when proving the “only if” direction of the reduction,
we define the partition $(V'_1, V'_2, V'_3)$ as $V'_i = \{x_e \mid i \notin C_e\} \cup \{y_v \mid c(v) = i\} \cup \{z_j, z'_j \mid (i-1)k + 1 \le j \le ik\}$. Therefore we obtain:

**Corollary 1.** Deciding whether the k-domatic number of a bipartite graph is at least 3 is N$P$-complete for every fixed positive integer k.

The following corollary is immediate.

**Corollary 2.** For every fixed integer $k \ge 1$, computing the k-domatic number of a bipartite graph is N$P$-hard.

## 3 Approximation Algorithm for k-Domatic Number

Since computing the k-domatic number is N$P$-hard, we are interested in designing approximation algorithms for it. In this section we present a logarithmic-factor approximation algorithm for computing the k-domatic number of a graph, generalizing the result of [5] for the 1-domatic number.

**Theorem 2.** For every fixed integer $k \ge 1$, the k-domatic number of a given graph of order $n$ can be approximated within a factor of $(\frac{1}{k} + o(1)) \ln n$ in polynomial time.

*Proof.* Fix an integer $k \ge 1$. Let $G = (V, E)$ be a graph of order $n \ge N_0$, where $N_0$ is a sufficiently large but fixed integer (which may depend on $k$). (Note that the k-domatic number of a graph of order $n \le N_0$ can be computed in constant time.) If $\delta(G) \le \ln n + 3k \ln \ln n$, due to Theorem 2.9 in [15], we have $d_k(G) \le \frac{\delta(G)}{k} + 1 \le (\frac{1}{k} + o(1)) \ln n$. In this case, a trivial k-domatic partition that consists of only V itself is already a $(\frac{1}{k} + o(1)) \ln n$ approximate solution. Therefore, we assume in what follows that $\delta(G) > \ln n + 3k \ln \ln n$.

Let $t = \delta(G)/(\ln n + 3k \ln \ln n)$. For every vertex $v \in V$, assign a label $l(v) \in \{1, 2, \dots, t\}$ to v uniformly at random; that is, $l(v) = i$ with probability $1/t$ for all $i \in \{1, 2, \dots, t\}$. Let $S_i$, $1 \le i \le t$, be the set of vertices that receive label $i$. Evidently $\{S_1, S_2, \dots, S_t\}$ is a partition of V. For $v \in V$ and $i \in \{1, 2, \dots, t\}$, let $\mathcal{E}(v, i)$ denote the event that at most $k-1$ neighbors of v have label $i$. If there is no $v \in V$ for which $\mathcal{E}(v, i)$ holds, then every vertex $v \in V$ has at least $k$ neighbors in $S_i$, and hence $S_i$ is a k-dominating set of G. For all $v \in V$ and $i \in \{1, 2, \dots, t\}$, we have

$$ \begin{aligned} \mathrm{Pr}[\mathcal{E}(v, i)] &= \sum_{j=0}^{k-1} \binom{\mathrm{deg}(v)}{j} \left(\frac{1}{t}\right)^j \left(1 - \frac{1}{t}\right)^{\mathrm{deg}(v)-j} \\ &\le \sum_{j=0}^{k-1} (\mathrm{deg}(v))^j \left(\frac{1}{t}\right)^j \left(1 - \frac{1}{t}\right)^{\mathrm{deg}(v)-j} \\ &= \left(1 - \frac{1}{t}\right)^{\mathrm{deg}(v)} \cdot \sum_{j=0}^{k-1} \left(\frac{\mathrm{deg}(v)}{t}\right)^{-1} \left(1 - \frac{1}{t}\right)^j, \end{aligned} $$
where the first inequality follows from the fact that $\binom{n_1}{n_2} \le n_1^{n_2}$ for two positive integers $n_1 \ge n_2$.

As $\frac{deg(v)}{t}(1 - \frac{1}{t})^{-1} = \frac{deg(v)}{t-1} \ge \frac{deg(v)}{\delta(G)} \ge 1$, we have

$$
\begin{align*}
\mathrm{Pr}[\mathcal{E}(v, i)] &\le \left(1 - \frac{1}{t}\right)^{deg(v)} \sum_{j=0}^{k-1} \left(\frac{deg(v)}{t} \left(1 - \frac{1}{t}\right)^{-1}\right)^{k-1} \\
&= \left(1 - \frac{1}{t}\right)^{deg(v)} \cdot k \cdot \left(\frac{deg(v)}{t}\right)^{k-1} \left(1 - \frac{1}{t}\right)^{-k+1} \\
&= k \left(1 - \frac{1}{t}\right)^{deg(v)-k+1} \left(\frac{deg(v)}{t}\right)^{k-1} \\
&\le k \cdot \exp\left(-\frac{deg(v)-k+1}{t} + (k-1)\ln\left(\frac{deg(v)}{t}\right)\right) \\
&\quad \text{(where we use } 1 + x \le e^x \text{ for all } x \in \mathbb{R}, \text{ and denote } \exp(m) := e^m\text{.)}
\end{align*}
$$

Define a function $f$ as $f(x) = -x + (k-1) \ln x$. Clearly $f$ is non-increasing on $[X_0, \infty)$ for some sufficiently large but fixed $X_0$ (depending on $k$ only). As $\frac{deg(v)}{t} \ge \frac{\delta(G)}{t} = \Omega(\ln n)$, by choosing large enough $n \ge N_0$ we have $f(\frac{deg(v)}{t}) \le f(\frac{\delta(G)}{t})$, and thus

$$
\begin{align*}
\mathrm{Pr}[\mathcal{E}(v, i)] &\le k \cdot \exp\left(-\frac{\delta(G)-k+1}{t} + (k-1)\ln\left(\frac{\delta(G)}{t}\right)\right) \\
&= k \cdot \exp\left(-\frac{\delta(G)-k+1}{\delta(G)/(\ln n + 3k \ln \ln n)} + (k-1)\ln\left(\frac{\delta(G)}{\delta(G)/(\ln n + 3k \ln \ln n)}\right)\right) \\
&= k \cdot \exp\left(-\left(\ln n + 3k \ln \ln n\right)\left(1 - O\left(\frac{1}{\ln n}\right)\right) + (k-1)\ln\left(\ln n + 3k \ln \ln n\right)\right) \\
&\quad \text{(where we use } \delta(G) > \ln n \text{ and } k = O(1)\text{)} \\
&\le \exp\left(-\ln n - 2k \ln \ln n + o(\ln \ln n)\right) \\
&\le \exp\left(-\ln n - k \ln \ln n\right) \\
&= n^{-1}(\ln n)^{-k}.
\end{align*}
$$

Call a pair $(v, i)$ bad if the event $\mathcal{E}(v, i)$ happens. By linearity of expectation, the expected number of bad pairs is

$$
\sum_{v \in V; 1 \le i \le t} \mathrm{Pr}[\mathcal{E}(v, i)] \le nt \cdot n^{-1}(\ln n)^{-k} = t \cdot o(1).
$$

Recall that $S_i = \{v \in V \mid l(v) = i\}$ for each $i \in \{1, 2, \dots, t\}$. Notice that $S_i$ is a $k$-dominating set of $G$ if and only if there is no $v \in V$ such that $(v, i)$ is a bad pair. Clearly a bad pair $(v, i)$ can “prevent” at most one such set, namely $S_i$, from being a $k$-dominating set of $G$. Hence, the expected number of $k$-dominating sets among $\{S_i \mid i \in \{1, 2, \dots, t\}\}$ is at least $t - t \cdot o(1) = (1 - o(1))t$. By checking the $t$ sets $S_1, S_2, \dots, S_t$ one by one, we can find all the $k$-dominating sets among
them. Add the vertices not covered by these sets to them arbitrarily. Then, we obtain a k-domatic partition of G of (expected) size $(1 - o(1))t$. This solution has an approximation factor of

$$ \frac{d_k(G)}{(1 - o(1))t} \le \frac{\frac{\delta(G)}{k} + 1}{(1 - o(1))\delta(G)/(\ln n + 3k \ln \ln n)} \le \left(\frac{1}{k} + o(1)\right) \ln n. $$

Finally we show that this algorithm can be efficiently derandomized by the method of conditional probabilities. Order the vertices in V arbitrarily, say $v_1, v_2, \dots, v_n$. We assign labels to the vertices according to this order, from $v_1$ to $v_n$. Suppose we are dealing with $v_i$, and the labels of $v_1, \dots, v_{i-1}$ have already been fixed to be $l_1, \dots, l_{i-1}$, respectively. We try all the possible labels $1, 2, \dots, t$ one by one, and assign $v_i$ with the label $l_i$ that minimizes the expected number of bad pairs conditioned on that $(\forall 1 \le s \le i) l(v_s) = l_s$. (Recall that $l(v)$ is the label of v; here we regard it as a random variable.) This expected number can be computed in polynomial time, because it is equal to

$$ \sum_{v \in V; 1 \le j \le t} \mathrm{Pr}[\mathcal{E}(v, j) \mid (\forall 1 \le s \le i) l(v_s) = l_s], $$

where, denoting by $r_j$ the number of neighbors of $v_i$ that has already been given label $j$, we have

$$ \mathrm{Pr}[\mathcal{E}(v, j)] = \begin{cases} 0, & \text{if } r_j \ge k; \\ 1, & \text{if } r_j < k \text{ and } \sum_{q=1}^{t} r_q = \mathrm{deg}(v); \\ \sum_{j'=0}^{k-1-r_j} \left( \mathrm{deg}(v) - \sum_{q=1}^{t} r_q \right) \left( \frac{1}{t} \right)^{j'} \left( 1 - \frac{1}{t} \right)^{\mathrm{deg}(v) - \sum_{q=1}^{t} r_q - j'}, & \text{otherwise.} \end{cases} $$

Since $k$ is fixed, we can compute every $\mathrm{Pr}[\mathcal{E}(v, j)]$ in polynomial time, and there are only $|V| \cdot t \le n^2$ of them.

By our choice of labels, after all labels have been determined, the number of bad pairs does not exceed the expected number of bad pairs estimated before. The remaining arguments go through analogously as before, and we can obtain a solution of approximation factor $(\frac{1}{k} + o(1)) \ln n$. This completes the proof of Theorem 2.

# 4 k-Domatic Number of Special Graphs

In this section we determine the exact values of the k-domatic number of some special classes of graphs. By Theorem 2.9 in [15], $d_k(G) \le \frac{\delta(G)}{k} + 1$. As $d_k(G)$ is a positive integer, we have $d_k(G) = 1$ whenever $k > \delta(G)$. Therefore, when considering $d_k(G)$ we only care those $k$ for which $2 \le k \le \delta(G)$. (The case $k = 1$ corresponds to the domatic number, which has been extensively studied in the literature.)

For every integer $n \ge 2$, let $F_n$ denote the fan graph with vertex set $V = \{v_0, v_1, v_2, \dots, v_n\}$ and edge set $E = \{v_i v_{i+1} \mid 1 \le i \le n-1\} \cup \{v_0 v_i \mid 1 \le i \le n\}$. Obviously $\delta(F_n) = 2$.
**Theorem 3.** Let $n \ge 2$ be an integer. Then,

$$d_2(F_n) = \begin{cases} 1 & \text{if } n \in \{2, 4\}; \\ 2 & \text{otherwise.} \end{cases}$$

*Proof.* We have $d_2(F_n) \le \delta(F_n)/2 + 1 = 2$. When $n$ is odd, it can be verified that $V_0 := \{v_i \mid 0 \le i \le n; i \text{ is even}\}$ and $V_1 := \{v_i \mid 0 \le i \le n; i \text{ is odd}\}$ are both 2-dominating sets of $F_n$, and clearly $(V_0, V_1)$ is a partition of $V$. Thus $d_2(F_n) = 2$ when $n$ is odd. If $n = 2$ or $4$, it can be checked exhaustively that $d_2(F_n) = 1$. Now consider the case where $n$ is even and $n \ge 6$. Let $Z_0 = \{v_i \mid 0 \le i \le n-4; i \text{ is even}\} \cup \{v_{n-1}\}$, and $Z_1 = V \setminus Z_0$. It is easy to see that for each $j \in \{0, 1\}$, every vertex in $Z_j$ is adjacent to at least two vertices in $Z_{1-j}$. Thus $Z_0$ and $Z_1$ are both 2-dominating sets of $G$, indicating that $d_2(F_n) \ge 2$. Hence $d_2(F_n) = 2$, and the proof of Theorem 3 is complete.

For every integer $n \ge 3$, let $W_n$ denote the wheel graph with vertex set $V = \{v_0, v_1, v_2, \dots, v_n\}$ and edge set $E = \{v_iv_{i+1} \mid 1 \le i \le n-1\} \cup \{vnv_1\} \cup \{v_0v_i \mid 1 \le i \le n\}$. Clearly $\delta(W_n) = 3$.

**Theorem 4.** $d_2(W_n) = 2$ for every integer $n \ge 3$.

*Proof.* Let $V_0 = \{v_i \mid 0 \le i \le n; i \text{ is even}\}$ and $V_1 = \{v_i \mid 0 \le i \le n; i \text{ is odd}\}$. It is easy to verify that $V_0$ and $V_1$ are both 2-dominating sets of $W_n$ (regardless of the parity of $n$), and thus $d_2(W_n) \ge 2$. On the other hand, we have $d_2(W_n) \le \lfloor \delta(W_n)/2 \rfloor + 1 = 2$. Hence $d_2(W_n) = 2$.

**Theorem 5.** $d_3(W_n) = 1$ for every integer $n \ge 3$.

*Proof.* First note that $d_3(W_n) \le \lfloor \delta(W_n)/3 \rfloor + 1 = 2$. Assume that $d_3(W_n) = 2$ and $(V_0, V_1)$ is a 3-domatic partition of $G$. Also assume without loss of generality that $v_0 \in V_0$. If $v_i \notin V_1$ for some $1 \le i \le n$, then all the three neighbors of $v_i$ must belong to $V_1$, implying that $v_0 \in V_1$ which is a contradiction. Thus $V_1 = \{v_1, v_2, \dots, v_n\}$ and $V_0 = \{v_0\}$. But then $V_0$ is not a 3-dominating set of $G$. Therefore $d_3(W_n) = 2$ cannot hold, and thus $d_3(W_n) = 1$.

## Acknowledgement

The author is grateful to the anonymous referees for their helpful suggestions on improving the presentation of this paper.

## References

1. Y. Caro and Y. Roditty. A note on the $k$-domination number of a graph. *Internat. J. Math. Math. Sci.*, 13:205–206, 1990.

2. E.J. Cockayne and S.T. Hedetniemi. Towards a theory of domination in graphs. *Networks*, 7:247–261, 1977.

3. R. Diestel. *Graph Theory*. Springer-Verlag, fourth edition, 2010.
4. O. Favaron, A. Hansberg, and L. Volkmann. On *k*-domination and minimum degree in graphs. *J. Graph Theory*, 57:33–40, 2008.

5. U. Feige, M.M. Halldórsson, G. Kortsarz, and A. Srinivasan. Approximating the domatic number. *SIAM J. Comput.*, 32(1):172–195, 2002.

6. J.F. Fink and M.S. Jacobson. *n*-domination in graphs. *Graph Theory with Applications to Algorithms and Computer Science*, pages 282–300, 1985.

7. J.F. Fink and M.S. Jacobson. On *n*-domination, *n*-dependence and forbidden subgraphs. *Graph Theory with Applications to Algorithms and Computer Science*, pages 301–311, 1985.

8. J. Fujisawa, A. Hansberg, T. Kubo, A. Saito, M. Sugita, and L. Volkmann. Independence and 2-domination in bipartite graphs. *Australas. J. Combin.*, 40:265–268, 2008.

9. S. Fujita, M. Yamashita, and T. Kameda. A study on *r*-configurations – a resource assignment problem on graphs. *SIAM J. Discrete Math.*, 13:227–254, 2000.

10. M.R. Garey and D.S. Johnson. *Computers and Intractability: A Guide to the Theory of NP-Completeness*. W. H. Freeman, 1979.

11. A. Hansberg, D. Meierling, and L. Volkmann. Distance domination and distance irredundance in graphs. *Electron. J. Comb.*, 14, 2007.

12. T.W. Haynes, S.T. Hedetniemi ST, and P.J. Slater. *Domination in Graphs: Advanced Topics*. Marcel Dekker, 1998.

13. T.W. Haynes, S.T. Hedetniemi ST, and P.J. Slater. *Fundamentals of Domination in Graphs*. Marcel Dekker, 1998.

14. K. Islam, S. G. Akl, and H. Meijer. Maximizing the lifetime of wireless sensor networks through domatic partition. In *Proceedings of the 34th IEEE Conference on Local Computer Networks (LCN)*, 2009.

15. K. Kämmerling and L. Volkmann. The *k*-domatic number of a graph. *Czech. Math. J.*, 59(2):539–550, 2009.

16. A. Meir and J.W. Moon. Relations between packing and covering number of a tree. *Pacific J. Math.*, 61:225–233, 1975.

17. R. Misra and C. Mandal. Efficient clusterhead rotation via domatic partition in self-organizing sensor networks. *Wireless Communications & Mobile Computing*, 9(8):1040–1058, 2009.

18. S. V. Pemmaraju and I. A. Pirwani. Energy conservation via domatic partition- s. In *Proceedings of the 7th ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc)*, 2006.

19. R. Pepper. Implications of some observations about the *k*-domination number. *Congr. Numer.*, 206:65–71, 2010.

20. D. Rautenbach and L. Volkmann. New bounds on the *k*-domination number and the *k*-tuple domination number. *Appl. Math. Lett.*, 20:98–102, 2007.

21. J.A. Telle. Complexity of domination-type problems in graphs. *Nord. J. Comput.*, 1(1):157–171, 1994.

22. B. Zelinka. On *k*-ply domatic numbers of graphs. *Math. Slovaca*, 34(3):313–318, 1984.