# Counting the Number of Domatic Partition of a Graph

Saeid Alikhani1,111Corresponding author Davood Bakhshesh2 Nima Ghanbari1

###### Abstract

A subset of vertices $S$ of a graph $G$ is a dominating set if every vertex in
$V\setminus S$ has at least one neighbor in $S$. A domatic partition is a
partition of the vertices of a graph $G$ into disjoint dominating sets. The
domatic number $d(G)$ is the maximum size of a domatic partition. Suppose that
$dp(G,i)$ is the number of distinct domatic partition of $G$ with cardinality
$i$. In this paper, we consider the generating function of $dp(G,i)$, i.e.,
$DP(G,x)=\sum_{i=1}^{d(G)}dp(G,i)x^{i}$ which we call it the domatic partition
polynomial. We explore the domatic polynomial for trees, providing a quadratic
time algorithm for its computation based on weak 2-coloring numbers. Our
results include specific findings for paths and certain graph products,
demonstrating practical applications of our theoretical framework.

1Department of Mathematical Sciences, Yazd University, 89195-741, Yazd, Iran

2Department of Computer Science, University of Bojnord, Bojnord, Iran

<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
Keywords: Domatic partition, dominating set, counting.

AMS Subj. Class.: 05C69.

##  1 Introduction

Let $G=(V,E)$ be a simple graph of order $n$. The open neighborhood (closed
neighborhood) of a vertex $v\in V$ is the set $N(v)$ = $\\{u|uv\in E\\}$, (the
set $N[v]$ = $N(v)\cup\\{v\\}$). The number of vertices in $|N(v)|$ is the
degree of $v$, denoted by $deg(v)$. A set $S\subseteq V$ is a dominating set
of a graph $G$, if every vertex in $V\setminus S$ has at least one neighbor in
$S$, in other words $N[S]=V$. The cardinality of a minimum dominating set in
$G$ is called the domination number of $G$ and is denoted by $\gamma(G)$. The
various different domination concepts are well-studied now, however new
concepts are introduced frequently and the interest is growing rapidly. We
recommend two fundamental books [5, 6] and some surveys [4, 7] about
domination in general.

A domatic partition is a partition of the vertex set into dominating sets, in
other words, a partition $\pi$ = $\\{V_{1},V_{2},...,V_{k}\\}$ of $V(G)$ such
that every set $V_{i}$ is a dominating set in $G$. Cockayne and Hedetniemi [2]
introduced the domatic number of a graph $d(G)$ as the maximum order $k$ of a
vertex partition. For more details on the domatic number refer to e.g., [8, 9,
10].

Motivated by enumerating of the number of dominating sets of a graph and
domination polynomial (see e.g. [1]), the enumeration of the domatic partition
for certain graphs is a natural subject. In other words, we explore domatic
partition from the point of view of the counting polynomial defined in the
following standard way.

###### Definition 1.1

Let ${\cal DP}(G,i)$ be the family of domatic partition of a graph $G$ with
cardinality $i$, and let $dp(G,i)=|{\cal DP}(G,i)|$. The domatic polynomial
$DP(G,x)$ of $G$ is defined as

$DP(G,x)=\sum_{i=1}^{d(G)}dp(G,i)x^{i},$

where $d(G)$ is the domatic number of $G$.

In Section 2, we explore various properties of the domatic polynomial. Moving
on to Section 3, we delve into the investigation of the domatic polynomial for
trees. Following that, in Section 4, we introduce a quadratic time algorithm
designed to compute the domatic polynomial of trees, accompanied by an
analysis of its time complexity. Lastly, we wrap up our paper with a
conclusion in the final section.

##  2 Introduction to domatic polynomial

In this section, we obtain some properties of domatic polynomial of a graph.
We need the following result:

###### Theorem 2.1

[2] For any graph $G$, $d(G)\leq\delta+1$, where $\delta$ is the minimum
degree of $G$.

Also, we need the following easy lemma. It is well known that if there is no
isolated vertex in the graph, i.e. $\delta\geq 1$, then the domatic number is
at least 2. For convenience, we present a proof.

###### Lemma 2.2

If $G$ is a connected graph, then $d(G)\geq 2$.

Proof.  Suppose that $G$ is a graph of order $n$, and $D$ is a dominating set
of that with minimum size. Since $G$ is connected, so by Ore’s Theorem
$\gamma(G)\leq\frac{n}{2}$. Let $D$ be a dominating set of $G$ with minimum
size. By the definition of dominating sets, then $\overline{D}$ is a
dominating set of $G$ too. So

$P=\\{D,\overline{D}\\}$

is a domatic partition of $G$, and therefore we have the result. $\square$

As an immediate result of definition of domatic number, $dp(G,i)=0$ for
$i>d(G)$. So the following definition is equivalent to the definition of
domatic polynomial of a graph by using Theorem 2.1:

###### Definition 2.3

Let ${\cal DP}(G,i)$ be the family of domatic partition of a graph $G$ with
cardinality $i$, and let $dp(G,i)=|{\cal DP}(G,i)|$. The domatic polynomial
$DP(G,x)$ of $G$ is defined as

$DP(G,x)=\sum_{i=1}^{\delta+1}dp(G,i)x^{i},$

where $\delta$ is the minimum degree of $G$.

As an immediate result of Definition 2.3, we have the following result.

###### Proposition 2.4

If $G$ has isolate vertices, then

$DP(G,x)=x.$

In [3], it was shown that finding domatic number of a graph is NP-complete.
Consequently, we have the following result.

###### Theorem 2.5

Computation of the domatic polynomial of a graph is NP-complete.

A weak $k$-coloring of a graph $G=(V,E)$ assigns a color
$c(v)\in\\{1,2,\ldots,k\\}$ to each vertex $v\in V$, such that each non-
isolated vertex is adjacent to at least one vertex with different color. So a
weak $2$-coloring of a graph is equivalent to finding a domatic partition of a
graph of size $2$. In the following, let ${\cal W}(G,2)$ be the family of weak
$2$-coloring of a graph $G$, and let $w_{2}(G)=|{\cal W}(G,2)|$. So
$dp(G,2)=w_{2}(G)$.

We conclude this section, with the following results which are immediately
obtained by the Definition 1.1.

###### Proposition 2.6

Let $G$ be a graph, and $d(G)=r$. The following holds:

  * (i)

$dp(G,1)=1.$

  * (ii)

$dp(G,2)$ is the number of weak 2-coloring of $G$.

  * (iii)

$DP(G,1)$ is the number of all domatic partition of $G$.

  * (iv)

$\frac{\mathrm{d^{r}}}{\mathrm{d}x^{\mathrm{r}}}DP(G,x)=r!dp(G,r).$

  * (v)

$\frac{\mathrm{d^{s}}}{\mathrm{d}x^{\mathrm{s}}}DP(G,x)=0,$ for $s>r$.

  * (vi)

Zero is a root of $DP(G,x)$, with multiplicity one.

##  3 Domatic Polynomial of Trees

In this section, we aim to compute the domatic polynomial for a given tree. By
Theorem 2.1 and Lemma 2.2, if $T$ is a tree, then $d(T)=2$. So we have the
following result:

###### Proposition 3.1

Let $T$ be a tree. Then $d(T)=2$, and $DP(T,x)=x+w_{2}(T)x^{2}$.

Let $T$ be a tree and $u$ be a support vertex. Let $ones(u)$ be the collection
of vertices that have a degree of 1 and share an edge with $u$. Let
$T_{u}^{-1}$ and $T_{u}^{-2}$ be two trees obtained from $T$ by removing the
vertices $ones(u)$ and $ones(u)\cup\\{u\\}$, respectively.

In a tree, we call a vertex $v$ as a quasi-star vertex of tree if it satisfies
the following conditions:

  * •

$v$ is adjacent to exactly one non-leaf vertex (an internal vertex).

  * •

$v$ is adjacent to at least one leaf (vertex with degree 1).

We call a tree containing a quasi-star vertex by star-neighbor tree. Now, we
prove the following result.

###### Theorem 3.2

For any star-neighbor tree $T$ of order $n\geq 4$, if $y$ is its quasi-star
vertex, then

$w_{2}(T)=w_{2}(T_{y}^{-1})+w_{2}(T_{y}^{-2}),$

where $w_{2}(K_{1,r})=1$, for any $r\geq 1$.

Proof.  It is clear that for any $r\geq 1$, $w_{2}(K_{1,r})=1$. Suppose that
$\cal{C}$ is a weak 2-coloring for tree $T$. We will show that with this
coloring, if we cannot construct a weak 2-coloring for tree $T_{y}^{-1}$, we
can certainly construct a weak 2-coloring for tree $T_{y}^{-2}$ using it.
Also, suppose that the non-leaf vertex adjacent to vertex $y$ is vertex $w$.
It is easy to see that if the colors of vertices $y$ and $w$ are different,
then coloring $\cal{C}$ is indeed a coloring for tree $T_{y}^{-1}$. Now,
assume that in coloring $\cal{C}$, the colors of the two vertices $y$ and $w$
are the same. Therefore, it is clear that since vertex $y$ is a leaf in tree
$T_{y}^{-1}$, coloring $\cal{C}$ is not a coloring for $T_{y}^{-1}$, but since
vertex $w$ must, by the definition of weak 2-coloring, be adjacent to a vertex
with a different color, one of the vertices adjacent to $w$ must have a
different color from $w$. Therefore, we conclude that coloring $\cal{C}$ is a
coloring for tree $T_{y}^{-2}$.

Based on the above discussion, we can derive the relationship $w_{2}(T)\leq
w_{2}(T_{y}^{-1})+w_{2}(T_{y}^{-2})$.

Now, since any coloring for tree $T_{y}^{-1}$ or $T_{y}^{-2}$ can easily be
transformed into a coloring for tree $T$, the above relationship is an exact
equality. Therefore, the theorem is proved. $\square$

Now, consider a path $P_{n}$. It is clear that $P_{n}$ is a star-neighbor
tree. Let $T:=P_{n}$. It is clear that $T_{y}^{-1}$ or $T_{y}^{-2}$ are
$P_{n-1}$ and $P_{n-2}$, respectively. Now, using Theorem 3.2, we have the
following result.

###### Corollary 3.3

For any path $P_{n}$ of order $n\geq 4$,

$w_{2}(P_{n})=w_{2}(P_{n-1})+w_{2}(P_{n-2}),$

where $w_{2}(P_{3})=w_{2}(P_{2})=1$.

As an immediate result of Corollary 3.3, we have:

###### Corollary 3.4

$\lim_{n\to\infty}\frac{w_{2}(P_{n+1})}{w_{2}(P_{n})}=\phi,$ where $\phi$ is
the golden ratio.

Proof.  Since $w_{2}(P_{n})$ follows the Fibonacci sequence, we have the
result. $\square$

Let $w_{1},w_{2},\ldots,w_{k}$ be some vertices of a graph $G$. Let
$B(G;w_{1},...,w_{k})$ be the bouquet of graph $G$ with respect to the
vertices $\\{w_{i}\\}_{i=1}^{k}$ and obtained by identifying the vertex
$w_{i}$ of the graph with vertex $w$.

Consider a tree denoted by $T$, and select a support vertex within $T$,
labeled $y$. Let $N(y)\setminus ones(y)=\\{w_{1},w_{2},\ldots,w_{k}\\}$. The
tree obtained by bouqueting the vertices $\\{w_{1},w_{2},\ldots,w_{k}\\}$ is
denoted as $T^{\prime}$ (see Figure 1).

Figure 1: A tree $T$ and the tree $T^{\prime}$.

Now, we prove the following result.

###### Theorem 3.5

For any tree $T$ of order $n>1$, if $y$ is one of its support vertices, then

$w_{2}(T)=w_{2}(T_{y}^{-1})+w_{2}({T^{\prime}}_{y}^{-2}).$

Proof.  Suppose that $\cal{C}$ is a weak 2-coloring for tree $T$. We will show
that with this coloring, if we cannot construct a weak 2-coloring for tree
$T_{y}^{-1}$, we can certainly construct a weak 2-coloring for tree
${T^{\prime}}_{y}^{-2}$ using it. Also, let $N(y)\setminus
ones(y)=\\{w_{1},w_{2},\ldots,w_{k}\\}$. It is easy to see that if the colors
of vertices $y$ and one of the vertices $\\{w_{1},w_{2},\ldots,w_{k}\\}$ are
different, then coloring $\cal{C}$ is indeed a coloring for tree $T_{y}^{-1}$.
Now, assume that in coloring $\cal{C}$, the colors of the vertices $y$ and all
vertices $\\{w_{1},w_{2},\ldots,w_{k}\\}$ are the same. Now, by bouqueting the
vertices $\\{w_{1},w_{2},\ldots,w_{k}\\}$ into a vertex $w$, we obtain the
tree $T^{\prime}$. We color the vertex $w$ by the color assigned to the
vertices $\\{w_{1},w_{2},\ldots,w_{k}\\}$. Since $w$ have the same color with
$y$, coloring $\cal{C}$ is not a coloring for ${T^{\prime}}_{y}^{-1}$, but
since the vertex $w$ in $T^{\prime}$ must, by the definition of weak
2-coloring, be adjacent to a vertex with a different color, one of the
vertices adjacent to $w$ must have a different color from $w$. Therefore, we
conclude that coloring $\cal{C}$ is a coloring for tree
${T^{\prime}}_{y}^{-2}$.

Based on the above discussion, we can derive the relationship
$w_{2}(T)=w_{2}(T_{y}^{-1})+w_{2}({T^{\prime}}_{y}^{-2})$.

Now, since any coloring for tree $T_{y}^{-1}$ or ${T^{\prime}}_{y}^{-2}$ can
easily be transformed into a coloring for tree $T$, the above relationship is
an exact equality. Therefore, the theorem is proved. $\square$

As an another conclusion of Theorem 3.5, we have the following result.

###### Proposition 3.6

If $P_{n}$ is a path of order $n$, then

$DP(P_{n}\circ K_{1},x)=x+2^{n-1}x^{2}.$

Proof.  It is not hard to see that by Theorem 3.5, $w_{2}(P_{n}\circ
K_{1})=2w_{2}(P_{n-1}\circ K_{1})$. Since $w_{2}(P_{2}\circ K_{1})=2$, we
easily conclude that $w_{2}(P_{n}\circ K_{1})=2^{n-1}$. Hence, $DP(P_{n}\circ
K_{1},x)=x+2^{n-1}x^{2}.$

Finally, we extend the previous result as follows.

###### Theorem 3.7

Let $G$ be a graph of order $n$, and let $r>0$ be an integer. Then

$DP(G\circ\overline{K}_{r},x)=x+2^{n-1}x^{2}.$

Proof.  Assume we have two colors $c_{1}$ and $c_{2}$ for coloring of $G$. As
we know, each vertex of the graph $G$ is adjacent to at least $r$ vertices of
degree one. Therefore, for a weak 2-coloring of $G$, any color assigned to
vertex $x$ must be different from the colors assigned to all its adjacent
vertices of degree one. Hence, the method of coloring is completely
determined. Now, since each vertex in $G$ has two coloring options, the total
number of ways to color (weak 2-coloring) the graph is $2^{n}$. However, by
swapping color $c_{1}$ with color $c_{2}$, we obtain another coloring, but in
terms of domatic partitioning, it is no different from the coloring before the
swap. Therefore, the total number of distinct weak 2-colorings of the graph is
$2^{n-1}$. Hence, $w_{2}(G\circ\overline{K}_{)}=2^{n-1}$ that completes the
proof. $\square$

##  4 Algorithm and analysis

Based on Theorem 3.5, we provide the following algorithm that computes the
$w_{2}(T)$ for a tree $T$.

Input: Tree $T$

Output: $w_{2}(T)$

1

2

3Function  _ComputeW2(_$T$_)_:

4 if  _$T$ has only one vertex_ then

5 return 0;

6

7 end if

8 Identify a support vertex $y$ in $T$;

9 Compute $ones(y)$ (vertices of degree 1 adjacent to $y$);

10 Compute $T_{y}^{-1}$ by removing vertices in $\text{ones}(y)$;

11 Compute ${T^{\prime}}$ by bouqueting the vertices
$\\{w_{1},w_{2},\ldots,w_{k}\\}$ in $T$;

12 Compute ${T^{\prime}}_{y}^{-2}$ by further removing vertex $y$ from
${T^{\prime}}_{y}^{-1}$;

13

14

15

16return ComputeW2(_$T_{y}^{-1}$_) \+ ComputeW2(_${T^{\prime}}_{y}^{-2}$_);

Algorithm 1 Algorithm to compute $w_{2}(T)$ in a tree $T$

Now, we analyze the time complexity of the algorithm.

To analyze the time complexity of the algorithm for computing $w_{2}(T)$ for a
tree $T$ of order $n$, we consider the following steps:

  * •

Step 1: Identifying a support vertex $y$:

    * –

Traversing the tree and checking the degrees of vertices takes $O(n)$ time.

  * •

Step 2: Computing ${ones}(y)$:

    * –

Identifying the vertices of degree 1 adjacent to $y$ can be done in $O(d_{y})$
time, where $d_{y}$ is the degree of $y$.

    * –

Since $d_{y}$ can be at most $n-1$, this step is bounded by $O(n)$.

  * •

Step 3: Computing $T_{y}^{-1}$:

    * –

Removing the vertices in ${ones}(y)$ involves visiting each of these vertices
and removing them, which can be done in $O(d_{y})$ time.

    * –

This step is bounded by $O(n)$ since $d_{y}\leq n-1$.

  * •

Step 4: Computing ${T^{\prime}}$:

    * –

Contracting vertices $\\{w_{1},w_{2},\ldots,w_{k}\\}$ into a single vertex
involves merging these vertices and updating the edges.

    * –

This can be done in $O(n)$ time.

  * •

Step 5: Computing ${T^{\prime}}_{y}^{-2}$:

    * –

Removing vertex $y$ from ${T^{\prime}}$ can be done in $O(1)$ time.

  * •

Step 6: Recursive computation of $w_{2}$:

    * –

The function $w_{2}$ is computed recursively on $T_{y}^{-1}$ and
${T^{\prime}}_{y}^{-2}$.

    * –

Let $n_{1}$ and $n_{2}$ be the sizes of the smaller subtrees formed after
removing vertices from $T$. The combined size is $n_{1}+n_{2}\leq n$.

The recurrence relation for the time complexity $T(n)$ is:

$T(n)=T(n_{1})+T(n_{2})+O(n).$

Using the Master Theorem for divide-and-conquer recurrences, we analyze this
recurrence:

  * •

Case 1: Balanced subproblems

$T(n)=2T\left(\frac{n}{2}\right)+O(n).$

According to the Master Theorem, this recurrence has a solution of
$T(n)=O(n\log n)$.

  * •

Case 2: Highly unbalanced subproblems

$T(n)=T(n-1)+O(n).$

This recurrence results in a time complexity of $T(n)=O(n^{2})$.

Now, we finalize this section.

###### Theorem 4.1

The worst-case time complexity of the algorithm for computing $w_{2}(T)$ for a
tree $T$ of order $n$ is $O(n^{2})$.

##  5 Conclusion

In this paper, we have introduced and analyzed the domatic partition
polynomial of a graph, $DP(G,x)$, which enumerates the domatic partitions of
$G$ by their cardinality. We have established several properties of this
polynomial, including its relationship with the minimum degree of the graph
and its computational complexity. Specifically, we demonstrated that computing
the domatic polynomial is NP-complete.

We also focused on trees and provided a detailed examination of their domatic
polynomials. We derived a quadratic time algorithm for computing the domatic
polynomial of a tree by leveraging the weak 2-coloring number, $w_{2}(T)$.
This algorithm capitalizes on the hierarchical structure of trees, recursively
breaking down the problem into smaller subtrees.

Furthermore, we provided specific results for paths and certain graph
products, showcasing the practical applications of our theoretical findings.
For paths $P_{n}$, we determined that
$DP(P_{n},x)=x+2^{\lfloor\frac{n}{2}\rfloor-1}x^{2}$. Additionally, we
extended our results to graphs of the form $G\circ\overline{K}_{r}$,
demonstrating that $DP(G\circ\overline{K}_{r},x)=x+2^{n-1}x^{2}$ for a graph
$G$ of order $n$.

Overall, our work provides a comprehensive framework for understanding and
computing the domatic partition polynomial, opening new avenues for future
research in graph theory and combinatorial optimization.

## References

  * [1] S. Akbari, S. Alikhani, Y.H. Peng, Characterization of graphs using domination polynomials, Eur. J. Combin. 31 (2010) 1714-1724.
  * [2] E.J. Cockayne, S.T. Hedetniemi, Towards a theory of domination in graphs, Networks, 7 (1977) 247-261.
  * [3] M.R. Garey, D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP- completeness, Freeman, San Francisco, CA, 197).
  * [4] W. Goddard, M.A. Henning, Independent domination in graphs: A survey and recent results, Discrete Math., 313 (7) (2013) 839-854.
  * [5] T.W. Haynes, S.T. Hedetniemi, P.J. Slater, Fundamentals of domination in graphs, Marcel Dekker, NewYork (1998).
  * [6] M.A. Henning, A. Yeo, Total domination in graphs. Springer Monographs in Mathematics, (2013).
  * [7] M.A. Henning, A survey of selected recent results on total domination in graphs. Discrete Math., 309 (1) (2009), 32-63.
  * [8] B. Zelinka, Domination in the generalized Petersen graphs, Czechoslov. Math. J., 52 (127) (2002), 11–16.
  * [9] B. Zelinka, Domatic number and degrees of vertices of a graph, Math. Slovaca 33 (1983): 145–147.
  * [10] B. Zelinka, On domatic numbers of graphs, Math. Slovaca 31 (1981), 91–95.