Domatically perfect graphs

Abstract

A graph $G$ of order $n$ is domatically perfect if $d\left(G\right)=n∕\gamma \left(G\right)$, where $\gamma \left(G\right)$ and $d\left(G\right)$ denote the domination number and the domatic number, respectively. In this paper, we give basic results for domatically perfect graphs, and study a main problem; for a given graph $G$, to find a necessary and sufficient condition for $G$ and its complement to be both domatically perfect. Moreover, we investigate domatically complete graphs, which are domatically full and domatically perfect.

Keywords:

• Domatically perfect
• Domination number
• Domatic number
• Domatically full
• Domatically complete

1 Introduction

All graphs considered in this paper are finite, simple, and undirected.

Let $G$ be a graph. We let $V\left(G\right)$ and $E\left(G\right)$ denote the vertex set and the edge set of $G$, respectively. For $x\in V\left(G\right)$, let $N_G\left(x\right)$ and $N_G\left[x\right]$ denote the open neighborhood and the closed neighborhood, respectively; thus $N_G\left(x\right)=\{y\in V\left(G\right):xy\in E\left(G\right)\}$ and $N_G\left[x\right]=N_G\left(x\right)\cup \left\{x\right\}$. Let $\delta \left(G\right)$ and $\Delta \left(G\right)$ denote the minimum degree and maximum degree of $G$, respectively. A graph $G$ is $k$-regular (or regular) if $\delta \left(G\right)=\Delta \left(G\right)=k$. For a graph $G$, the complement of $G$ is denoted by $\overline{G}$. For $X\subseteq V\left(G\right)$, we let $G\left[X\right]$ denote the subgraph of $G$ induced by $X$. For other basic terminology in Graph Theory, we refer to [1].

A subset $X$ of $V\left(G\right)$ is a dominating set of $G$ if $V\left(G\right)={\bigcup }_{x\in X}{N}_G\left[x\right]$. The minimum cardinality of a dominating set of $G$, denoted by $\gamma \left(G\right)$, is called the domination number of $G$. A dominating set of $G$ with the cardinality $\gamma \left(G\right)$ is called a $\gamma$-set of $G$. The domination number of graphs has been well studied for many years. The literature on domination number is surveyed in the two books [2,3].

A domatic partition of $G$ is a partition of $V\left(G\right)$ into classes that are pairwise disjoint dominating sets. The domatic number of $G$, denoted by $d\left(G\right)$, is the maximum cardinality of a domatic partition of $G$. The domatic number was introduced by Cockayne and Hedetniemi [4]. For a survey of results on domatic number, we refer to Chapter 13 in [3] by Zelinka.

Theorem 1.1

[4] For any graph $G$ of order $n$ , the following hold:

(1)	$d\left(G\right)\le \delta \left(G\right)+1$
(2)	$d\left(G\right)\le n∕\gamma \left(G\right)$

Definition 1.1

A graph $G$ is domatically full if $d\left(G\right)=\delta \left(G\right)+1$.

The concept of domatically full graph was introduced in [4]. Domatically full graphs are well studied; see [5–7] for example. In this paper, we consider the graphs satisfying the equality in Theorem 1.1(2).

Definition 1.2

A graph $G$ is domatically perfect if $d\left(G\right)=n∕\gamma \left(G\right)$.

By the definition, we immediately see the following for domatically perfect graphs.

Observation 1.1

The complete graph and its complement are domatically perfect.

Observation 1.2

Every vertex of a domatically perfect graph $G$ belongs to a $\gamma$ -set of $G$ .

Observation 1.3

If $G$ is a domatically perfect graph of order $n$ , then $\gamma \left(G\right)$ divides $n$ .

It follows from Observation 1.1 the domatically perfectness does not depend on the density of graphs. On the other hand, by Observation 1.2, domatically perfect graphs seem to be related to the criticality of graphs for the domination number or domatic number. The domatically perfect seems to be a very natural concept for the study on domination in graphs. However, as far as we know, domatically perfect graphs have not yet been exactly studied. So we thoroughly investigate domatically perfect graphs in this paper.

The paper is organized as follows. In Section 2, introducing several fundamental results, we consider domatically perfect graphs $G$ such that $\overline{G}$ is also domatically perfect, and describe the relation between domatically perfect and several criticality properties. In Section 3, for several pairs of graphs, we prove a necessary and sufficient condition for Cartesian products of them to be domatically perfect. In Section 4, we consider a domatically complete graph, which satisfies both equalities in Theorem 1.1. Furthermore, we also propose open problems in not only the final section but also in several sections.

2 Domatically perfect graphs

In addition to two observations in the previous, we prepare more observations for domatically perfect graphs.

Observation 2.1

For any domatically perfect graph $G$ , $\left|V\left(G\right)\right|\le \gamma \left(G\right)(\delta \left(G\right)+1)$ .

Observation 2.2

Let $G$ be a domatically perfect graph. Then the following hold:

(i)	$\gamma \left(G\right)=1$ if and only if $G=K_n$ .
(ii)	$d\left(G\right)=1$ if and only if $G={\overline{K}}_n$ .

Let $P_n$ (resp., $C_n$) denote a path (resp., a cycle) of order $n$. It is known that $\gamma \left(P_n\right)=\lceil n∕3\rceil$ and $\gamma \left(C_n\right)=\lceil n∕3\rceil$. So, for any $n\ge 5$, if the path $P_n$ (or the cycle $C_n$) is domatically perfect, then $\gamma \left(P_n\right)=\gamma \left(C_n\right)=n∕3$, that is, $d\left(P_n\right)=d\left(C_n\right)=3$. Thus, we have the following.

Observation 2.3

A path $P_n$ with $n\ge 1$ is domatically perfect if and only if $n=1,2$ or $n=4$ .

Observation 2.4

A cycle $C_n$ with $n\ge 3$ is domatically perfect if and only if $n\equiv 0(mod3)$ or $n=4$ .

It is proved by Ore [8] that every tree $T$ of order $n\ge 2$ is $\gamma \left(T\right)\le n∕2$. Since $d\left(T\right)\le 2$ by Theorem 1.1, if $T$ is domatically perfect, then $\gamma \left(T\right)=\frac{n}{2}$. Moreover, a connected graph of order $n$ with domination number $\frac{n}{2}$ is completely characterized, as follows. The corona of a graph $H$ is obtained from $H$ by joining an additional vertex of degree 1 to each vertex of $H$.

Theorem 2.1

Fink et al. [9]; Payan and Xuong [10] Let $G$ be a connected graph of order $n$ . Then $\gamma \left(G\right)=n∕2$ if and only if $G$ is either $C_4$ or a corona of a connected graph.

Corollary 2.1

A tree $T$ of order $n$ is domatically perfect if and only if $T$ is either $K_1$ or the corona of a tree.

As described in the previous section, it seems to be difficult to check the domatically perfectness of graphs, using the number of edges of graphs. In fact, by Observation 1.1, a complete graph and its complement are both domatically perfect. However, in general, this property does not hold, i.e., there exists a graph $G$ such that $G$ is domatically perfect but $\overline{G}$ is not: Let $K_{3,3,2}$ be the complete 3-partite graph with partite sets $V_1=\{a,b,c\},V_2=\{a^{\prime },b^{\prime },c^{\prime }\}$ and $V_3=\{x,y\}$. Let $G$ be the graph obtained from the $K_{3,3,2}$ by removing two edges $ax$ and $a^{\prime }y$. Observe that $\gamma \left(G\right)=2$ and $d\left(G\right)=4$ but that $\gamma \left(\overline{G}\right)=2$ and $d\left(\overline{G}\right)=1$, since $\{a,a^{\prime }\}$ is a (unique) $\gamma$-set of $\overline{G}$. Thus the following problem is difficult and interesting.

Problem 2.1

Find a necessary and sufficient condition for a given graph and its complement to be both domatically perfect.

Now we shall give solutions of Problem 2.1 for several graph families. As a corollary of Observation 2.2, for every graph $G$ with $\gamma \left(G\right)=n$, $G$ and $\overline{G}$ are both domatically perfect. Similarly to the above, we have the same conclusion for graphs with domination number a half of the order.

Proposition 2.1

Let $G$ be a connected graph of order $n$ with $\gamma \left(G\right)=\frac{n}{2}$ . Then $G$ and $\overline{G}$ are both domatically perfect.

Proof

By Theorem 2.1, $G$ is $C_4$ or a corona of a connected graph. If $G=C_4$, then since $\overline{G}$ consists of two independent edges, the corollary clearly holds. So we suppose that $G$ is a corona of a connected graph $H$. Let $v_1,v_2,\dots ,v_{\frac{n}{2}}$ be vertices of degree 1 in $G$ which are adjacent to vertices $u_1,u_2,\dots ,u_{\frac{n}{2}}$ in $H$. Since two disjoint sets $S_v={\bigcup }_{i=1}^{n∕2}\left\{v_i\right\}$ and $S_u={\bigcup }_{i=1}^{n∕2}\left\{u_i\right\}$ are minimum dominating sets of $G$, $G$ is domatically perfect. In the complement of $G$, For each $i\in \{1,2,\dots ,\frac{n}{2}\}$, $v_i$ is adjacent to all vertices but not to only one vertex $u_i$. Thus, for each $i\in \{1,2,\dots ,\frac{n}{2}\}$, $\{v_i,u_i\}$ is a minimum dominating set of $\overline{G}$; note that since $\delta \left(G\right)\ge 1$, $\gamma \left(\overline{G}\right)\ge 2$. Therefore, since $d\left(G\right)=\frac{n}{2}$, $\overline{G}$ is also domatically perfect. □

Corollary 2.2

For a tree $T$ with order $n\ge 1$ , if $T$ is both domatically perfect, then so is $\overline{T}$ .

Corollary 2.3

For a cycle $C_n$ with $n\ge 3$ , $C_n$ and $\overline{C_n}$ are both domatically perfect if and only if $n=3,4$ or $n\equiv 0(mod6)$ .

Proof

By Observation 2.4, the “if part” immediately holds and we have $n=4$ or $n\equiv 0(mod3)$. Moreover, since $\gamma \left(\overline{C_n}\right)=2$ if $n\ge 5$, $n\equiv 0(mod2)$ by the domatically perfectness of $\overline{C_n}$. Thus, we have the conclusion. □

In general, it seems to be not easy to determine whether the complement of a given tree is domatically perfect. So we give necessary and sufficient conditions for a path and trees with small diameter, as follows. A double star, denoted by $S_{a,b}$, is a tree with diameter 3 and a degree sequence $(a+1,b+1,1,1,\dots ,1)$.

Proposition 2.2

For a path $P_n$ of order $n\ge 1$ , $\overline{P_n}$ is domatically perfect if and only if $n=1$ or $n\equiv 0(mod2)$ .

Proof

The proposition is clear if $n=1$, and so, we suppose that $n\ge 2$. By observing $\gamma \left(\overline{P_n}\right)=2$, the “only-if part” immediately holds. Thus we prove the “if part”.

Let $P_n=v_0{v}_1\cdots v_{n-1}$. Note that for each $i\in \{1,\dots ,n-2\}$, $v_i$ is adjacent to all vertices but $v_{i-1}$ and $v_{i+1}$ in $\overline{P_n}$. Therefore, since now $n\equiv 0(mod2)$, $\{v_j,v_{j+1}\}$ forms a dominating set of $\overline{P_n}$ for each $j\in \{0,2,\dots ,n-2\}$, and hence, the proposition holds. □

Theorem 2.2

For a tree $T$ of order $n\ge 1$ with diameter at most $3$ , $\overline{T}$ is domatically perfect if and only if $T=P_2$ or $S_{r,r}$ for some integer $r\ge 1$ .

Proof

(If part) Since the former holds by Observation 2.3, we may suppose that $T=S_{r,r}$ for some integer $r\ge 1$. Let $u,v$ be two vertices of degree $r+1$ and let $L_u=p_1,p_2,\dots ,p_r$ (resp., $L_v=q_1,q_2,\dots ,q_r$) be the set of vertices of degree 1 adjacent to $u$ (resp., $v$). Observe that in the complement $\overline{S_{r,r}}$, $u$ (resp., $v$) is adjacent to all vertices in $L_v$ (resp., $L_u$) and every vertex in $L_u$ (resp., $L_v$) is adjacent to all vertices but $u$ (resp., $v$). Therefore, $\{u,v\}$ and $\{p_i,q_i\}$ for each $i\in \{1,2,\dots ,r\}$ are dominating sets of $\overline{S_{r,r}}$. Since $\gamma \left(\overline{S_{r,r}}\right)=2$ and $d\left(\overline{T}\right)=\frac{n}{2}$, $\overline{S_{r,r}}$ is domatically perfect.

(Only-if part) If the diameter of $T$ is one, then the theorem is trivial. Moreover, if it is two, then $T$ is isomorphic to a star and it is easy to see that every star of order at least 3 cannot be domatically perfect; note that every leaf of $T$ is not adjacent to the unique center vertex. Thus we suppose that the diameter of $T$ is exactly 3, i.e., it is a double star $S_{a,b}$ for some positive integers $a$ and $b$.

Suppose to the contrary that $a>b$. Let $u,v$ be two vertices in $S_{a,b}$ of degree at least $2$ and by symmetry, let $L_u=p_1,p_2,\dots ,p_a$ (resp., $L_v=q_1,q_2,\dots ,q_b$) be the set of vertices of degree 1 adjacent to $u$ (resp., $v$). Again observe that every vertex in $A=L_u\cup \left\{v\right\}$ is not adjacent to $u$ and one in $B=L_v\cup \left\{u\right\}$ is not adjacent to $v$. Thus, in the complement of $S_{a,b}$, we need to choose exactly one each of $A$ and $B$ to dominate all vertices by exactly two vertices (since $\gamma \left(\overline{S_{a,b}}\right)=2$). However, since $\left|A\right|>\left|B\right|$ by the assumption, $\overline{S_{a,b}}$ cannot be domatically perfect, a contradiction. □

Next we give a necessary and sufficient condition for a complete multipartite graph and its complement to be both domatically perfect, preparing the following lemma.

Lemma 2.1

Let $G$ be a complete $k$ -partite graph with $k\ge 2$ and each partite set of size at least $2$ . Then $G$ is domatically perfect if and only if $G$ has a perfect matching.

Proof

(If part) Let $M=\{e_1,e_2,\dots ,e_{\left|V\left(G\right)\right|∕2}\}$ be a perfect matching of $G$, and let $e_i=u_i{v}_i$ for each $i$. Note that each set $S_i=\{u_i,v_i\}$ is a $\gamma$-set of $G$. Since $\left|M\right|=\left|V\left(G\right)\right|∕2$, $G$ is domatically perfect.

(Only-if part) We prove this part by induction on $\left|V\left(G\right)\right|$. (Note that $\left|V\left(G\right)\right|$ is even and at least 4 since $d\left(G\right)=\left|V\left(G\right)\right|∕2$ by assumption.) If $\left|V\left(G\right)\right|=4$, then the lemma is clear. So we suppose that the lemma holds if $\left|V\left(G\right)\right|<n$, and that $\left|V\left(G\right)\right|=n$.

Let $S$ be a $\gamma$-set of a domatic partition of $G$. If $G\left[S\right]=K_2$, then since $G-S$ has a perfect matching $M^{\prime }$ by induction, $M^{\prime }\cup E\left(G\left[S\right]\right)$ is a perfect matching of $G$. Thus we may suppose that each $\gamma$-set of a domatic partition of $G$ induces $\overline{K_2}$.

Observe that if a partite set $R$ of $G$ has at least three vertices, then there exists no $\gamma$-set of $G$ consisting of only vertices in $R$ (since they cannot dominate a vertex in $R$). So every partite set of $G$ contains exactly two vertices, that is, $G$ is a complete $\frac{n}{2}$-partite graph $K_{2,2,\dots ,2}$ with partite sets $V_1,V_2,\dots ,V_{\frac{n}{2}}$. Therefore it is easy to see that $G$ has a perfect matching (cf. [11]). □

Theorem 2.3

Let $G$ be a complete $k$ -partite graph with $k\ge 2$ and partite sets $V_1,V_2,\dots ,V_k$ . Then $G$ and $\overline{G}$ are both domatically perfect if and only if for any $i,j\in \{1,2,\dots ,k\}$ , the following hold: $$\left\{\begin{array}{cc}\left|V_i\right|=\left|V_j\right|\hfill & (k:even)\hfill \\ \left|V_i\right|\mathrm{is}\mathrm{even}\mathrm{and}\left|V_i\right|=\left|V_j\right|\hfill & (k:odd)\hfill \end{array}\right.$$

Proof

(If part) If $\left|V_i\right|=1$, then the theorem holds by Observation 2.2. If $\left|V_i\right|\ge 2$, then $\gamma \left(G\right)=2$. Since now each partite set has the same size (even size if $k$ is odd), $G$ has a perfect matching (cf. [11]). Thus, by Lemma 2.1, $G$ is domatically perfect. On the other hand, $\gamma \left(\overline{G}\right)=k$ since $\overline{G}$ consists of $k$ connected components where each component is $K_{\left|V_i\right|}$. Therefore we have $\gamma \left(\overline{G}\right)d\left(\overline{G}\right)=k\cdot \left|V_i\right|=\left|V\left(G\right)\right|$, and hence, $\overline{G}$ is domatically perfect.

(Only-if part) If $\gamma \left(G\right)=1$, then the theorem holds since $G=K_k$ by Observation 2.2. So suppose that $\gamma \left(G\right)=2$, i.e., $\left|V_i\right|\ge 2$ for each $i\in \{1,2,\dots ,k\}$. Since $\overline{G}$ is domatically perfect, every two connected components of $\overline{G}$ must be the same size, otherwise $\gamma \left(\overline{G}\right)\cdot d\left(\overline{G}\right)=k\cdot p<\left|V\left(G\right)\right|$ where $p=min\{\left|V_i\right|:i\in \{1,2,\dots ,k\}\}$, a contradiction. Therefore, all partite sets have the same size (and in particular, the size is even if $k$ is odd since $G$ has a perfect matching, by Lemma 2.1), and hence, the theorem holds. □

In the rest of this section, we describe the criticality of domatically perfect graphs. For a graph $G$ and a vertex $u\in V\left(G\right)$, $G-u$ denotes the graph obtained from $G$ by removing $u$ and all edges incident to $u$, and for an edge $e\notin E\left(G\right)$, $G+e$ denotes the graph obtained from $G$ by adding $e$. A graph $G$ is vertex critical (resp., edge critical) if $\gamma (G-v)=\gamma \left(G\right)-1$ (resp., $\gamma (G+e)=\gamma \left(G\right)-1$) for any vertex $v\in V\left(G\right)$ (resp., any edge $e\notin E\left(G\right)$). A graph $G$ is domatically $k$ -critical if $k-1=d(G-e)<d\left(G\right)=k$ for every edge $e\in E\left(G\right)$.

The vertex critical, edge critical and domatically $k$-critical are introduced in [12,13] and [14], respectively. So far, those are well studied (for example, see [12,15–18] and [19], respectively), and Haynes and Henning [20] classified graphs resulting from deletion or addition of vertices and edges with respect to their domination number. Furthermore, Rall [19] discovers a relation between domatically critical and domatically full. We introduce several observations and results for vertex critical or edge critical graphs.

Observation 2.5

[20] Let $G$ be a graph. If $\gamma (G-v)\ne \gamma \left(G\right)$ for any vertex $v$ , then $\gamma (G-v)=\gamma \left(G\right)-1$ .

Observation 2.6

[20] Let $G$ be an edge critical graph. Then $\gamma (G-v)=\gamma \left(G\right)$ or $\gamma (G-v)<\gamma \left(G\right)$ holds for any vertex $v\in V\left(G\right)$ .

Observation 2.7

[19] Let $G$ be a graph with at least one edge. Then $d\left(G\right)-1\le d(G-e)\le d\left(G\right)$ for any edge $e\in E\left(G\right)$ .

Theorem 2.4

[19] Every domatically $3$ -critical graph is domatically full. Furthermore, for each $n\ge 4$ , there exists a graph which is domatically $n$ -critical but not domatically full.

Theorem 2.5

[14] Let $G$ be a domatically critical graph with domatic number $d\left(G\right)=k$ . Then $V\left(G\right)$ is the union of $k$ pairwise disjoint dominating sets $V_1,V_2,\dots ,V_k$ such that for any two distinct numbers $i,j\in \{1,2,\dots ,k\}$ , $G[V_i\cup V_j]$ is a bipartite graph on the sets $V_i$ and $V_j$ all of whose connected components are stars.

In what follows, we give several results for the criticality of domatically perfect graphs.

Proposition 2.3

Let $G$ be a domatically perfect graph of order $n\ge 2$ . Suppose that $G$ is neither $K_n$ nor ${\overline{K}}_n$ . If $\gamma (G-v)=\gamma \left(G\right)$ for a vertex $v\in V\left(G\right)$ , then $G-v$ is not domatically perfect.

Proof

Suppose to the contrary that $G-v$ is domatically perfect. Since $n-1=\gamma \left(G\right)d\left(G\right)-1=\gamma \left(G\right)d(G-v)$, we have $\gamma \left(G\right)(d\left(G\right)-d(G-v))=1$. However, this equality does not hold since $\gamma \left(G\right)\ge 2$ and $d\left(G\right)-d(G-v)$ is an integer. □

Corollary 2.4

Let $G$ be a domatically perfect graph of order $n\ge 2$ . Suppose that $G$ is neither $K_n$ nor ${\overline{K}}_n$ . If $G-v$ is domatically perfect for any vertex $v\in V\left(G\right)$ , then $G$ is vertex critical.

Proposition 2.4

Let $G$ be a domatically perfect graph of order $n\ge 2$ . Then $G$ is edge critical if and only if $G+e$ is not domatically perfect for any edge $e\in E\left(G\right)$ .

Proof

(If part) Suppose that $G$ is not edge critical, that is, $\gamma (G+e)=\gamma \left(G\right)$ for some $e\in E\left(G\right)$. Since $G$ is domatically perfect, $n=\gamma \left(G\right)d\left(G\right)=\gamma \left(G\right)d(G+e)$. Clearly, this equality means that $G+e$ is domatically perfect.

(Only-if part) If $G+e$ is domatically perfect, then $n=\gamma (G+e)d\left(G\right)=(\gamma \left(G\right)-1)d\left(G\right)<\gamma \left(G\right)d\left(G\right)=n$ since $G$ is edge critical, a contradiction. □

Corollary 2.5

Let $G$ be a domatically perfect graph of order $n\ge 2$ . If $G+e$ is not domatically perfect for any edge $e\in E\left(G\right)$ , then $\gamma (G-v)=\gamma \left(G\right)$ or $\gamma (G-v)<\gamma \left(G\right)$ holds for any vertex $v\in V\left(G\right)$ .

Proposition 2.5

For any integer $m\ge 2$ , there exists a graph which is domatically $m$ -critical but not domatically perfect.

Proof

Consider the graph $G=K_{m-1}+{\overline{K}}_t$ which is obtained from two graphs $K_{m-1}$ and ${\overline{K}}_t$ by joining each vertex of $K_{m-1}$ and that of ${\overline{K}}_t$. It is easy to check that $G$ is domatically $m$-critical. By assuming $t\ge 2$, the number of vertices becomes greater than $\gamma \left(G\right)d\left(G\right)=m$ since $\gamma \left(G\right)=1$, that is, it is not domatically perfect. □

Theorem 2.6

Let $G$ be a domatically perfect graph of order $n\ge 2$ . Then $G$ is domatically $2$ -critical if and only if $G$ is isomorphic to the complement of the complete $\gamma \left(G\right)$ -partite graph with each partite set of size $2$ .

Proof

Since the “if part” is trivial, it suffices to show the “only-if part”. Since $G$ is domatically perfect, $n=\gamma \left(G\right)d\left(G\right)=2\gamma \left(G\right)$. Let $V_1$ and $V_2$ be disjoint $\gamma$-sets of $G$; note that $V\left(G\right)=V_1\cup V_2$. By Theorem 2.5, $G(=G[V_1\cup V_2])$ is bipartite and each connected component in $G$ is a star. In particular, since $\left|V_1\right|=\left|V_2\right|$ and both sets are $\gamma$-sets, each component in $G$ must be $K_2$ (otherwise $\left|V_1\right|\ne \left|V_2\right|$ since the set of center vertices of stars is a $\gamma$-set). Therefore, the theorem holds. □

3 Cartesian products of graphs

In this section, we focus on a pair of graphs such that the Cartesian product of them is domatically perfect. There is a huge literature of the study on domination in Cartesian products of graphs since it is related to Vizing’s conjecture [21]. For more details, see a survey [22].

Definition 3.1

The Cartesian product of $G$ and $H$, denoted by $G\square H$, is a graph such that

•	$V(G\square H)=V\left(G\right)\times V\left(H\right)$, and
•	any two vertices $(u,u^{\prime })$ and $(v,v^{\prime })$ are adjacent in $G\square H$ if and only if either $u=v$ and $u^{\prime }{v}^{\prime }\in E\left(H\right)$ or $u^{\prime }=v^{\prime }$ and $uv\in E\left(G\right)$.

We first consider Cartesian products of a graph and a complete graph.

Theorem 3.1

For any $m,n\ge 1$ , $K_m\square K_n$ is domatically perfect.

Proof

Without loss of generality, we may assume that $m\ge n$. Observe that $\gamma (K_m\square K_n)=n$. Let $V\left(K_m\right)=\{u_0,u_1,\dots ,u_{m-1}\}$ and $V\left(K_n\right)=\{v_0,v_1,\dots ,v_{n-1}\}$. Then we can construct a partition $S_0,S_1,\dots ,S_{m-1}$ of $V(K_m\square K_n)$, as follows. $$S_i=\{(u_i,x):x\in V\left(K_n\right)\}\mathrm{for}i\in \{0,1,\dots ,m-1\}$$It is easy to check that $S_i$ is a $\gamma$-set of $K_m\square K_n$ for each $i\in \{0,1,\dots ,m-1\}$, i.e., $d(K_m\square K_n)=m$. Thus the theorem holds. □

Similarly to Theorem 3.1, we also see the following.

Proposition 3.1

For any $n\ge 3$ and $k\ge 1$ , $K_n\square P_k$ is domatically perfect.

Proposition 3.2

For any $n\ge 3$ and $k\ge 3$ , $K_n\square C_k$ is domatically perfect.

Corollary 3.1

For any $n\ge 3$ , $C_3\square C_n$ is domatically perfect.

We next focus on the Cartesian products of several pairs of paths and cycles. To consider whether those graphs are domatically perfect, we introduce an observation and known results for their domination number.

Observation 3.1

Every domatic partition of a domatically perfect graph consists of only $\gamma$ -sets.

Theorem 3.2

[23] $\gamma (P_2\square P_n)=\lceil (n+1)∕2\rceil$ for any $n\ge 1$ .

Theorem 3.3

[23] $\gamma (C_4\square C_n)=n$ for any $n\ge 4$ .

Theorem 3.4

$P_2\square P_n$ is domatically perfect if and only if $n=1,2$ or $n\equiv 0(mod3)$ .

Proof

(If part) Since the case when $n=1$ or $n=2$ is trivial, we assume that $n\equiv 0(mod3)$. Let $P_2=xy$ and $P_n=v_0{v}_1{v}_2\dots v_{n-1}$. Then we construct a partition $V(P_2\square P_n)=S_0\cup S_1\cup S_2$, as follows: $$S_0=\{(x,v_i):i\equiv 0(mod3)\}\cup \{(y,v_i):i\equiv 2(mod3)\}$$ $$S_1=\{(x,v_i):i\equiv 1(mod3)\}\cup \{(y,v_i):i\equiv 1(mod3)\}$$ $$S_2=\{(x,v_i):i\equiv 2(mod3)\}\cup \{(y,v_i):i\equiv 0(mod3)\}$$For each $j\in \{0,1,2\}$, it is easy to check that $S_j$ is a dominating set and that by Theorem 3.2, $S_j$ is also a $\gamma$-set since $\left|S_j\right|=\lceil (n+1)∕2\rceil$. Since $d(P_2\square P_n)\le 3$, $P_2\square P_n$ is domatically perfect.

(Only-if part) Suppose that $G=P_2\square P_n$ is domatically perfect. Now we may suppose that $n\ge 3$. By Observation 3.1, each domatic partition of $G$ consists of only $\gamma$-sets, that is, each element of the partition has order $\lceil (n+1)∕2\rceil$ by Theorem 3.2. Moreover, $d\left(G\right)=3$ since otherwise, i.e., if $d\left(G\right)=2$, then $\lceil (n+1)∕2\rceil =\left|V\left(G\right)\right|∕2=n$ since $G$ is domatically perfect, a contradiction (by $n\ge 3$). Then we have $3\lceil (n+1)∕2\rceil =\left|V\left(G\right)\right|=2n$, which means $n\equiv 0(mod3)$. □

Theorem 3.5

$C_4\square C_n$ with $n\ge 4$ is domatically perfect.

Proof

Let $C_4=u_0{u}_1{u}_2{u}_3$ and $C_n=v_0{v}_1{v}_2\dots v_{n-1}$. We construct a partition of $V(C_4\square C_n)=S_0\cup S_1\cup S_2\cup S_3$, as follows. $$S_0=\{(u_0,v_i):i\equiv 0(mod2)\}\cup \{(u_2,v_i):i\equiv 1(mod2)\}$$ $$S_1=\{(u_1,v_i):i\equiv 0(mod2)\}\cup \{(u_3,v_i):i\equiv 1(mod2)\}$$ $$S_2=\{(u_2,v_i):i\equiv 0(mod2)\}\cup \{(u_0,v_i):i\equiv 1(mod2)\}$$ $$S_3=\{(u_3,v_i):i\equiv 0(mod2)\}\cup \{(u_1,v_i):i\equiv 1(mod2)\}$$For each $j\in \{0,1,2,3\}$, it is easy to check that $S_j$ is a dominating set and that by Theorem 3.3, $S_j$ is also a $\gamma$-set since $\left|S_j\right|=n$. So we have $d(C_4\square C_n)=4$, and hence, the theorem holds. □

Klavžar and Seifter [23] also estimate the domination number of the Cartesian product of $C_5$ and $C_n$ for $n\ge 5$. However, the domination number is not exactly determined for some case when $n\equiv 3$ modulo 5. So we do not try to show the theorem which states whether $C_5\square C_n$ is domatically perfect, since the proof of the results might be a complicated case-by-case argument.

By the above results, one intuitively guesses that the Cartesian product of two domatically perfect graphs is also domatically perfect. However, the following implies that there exist counterexamples of small order for the expectation.

Proposition 3.3

$P_i\square P_j$ is not domatically perfect if $i,j\in \{2,4\}$ , unless $i=j=2$ .

Proof

By symmetry, it suffices to prove two cases (i) $i=2$ and $j=4$ and (ii) $i=j=4$. By Theorem 3.4, the case (i) is already proved. For the case (ii), it is easy to see that $3<\gamma (P_4\square P_4)=4$. However, since $d(P_4\square P_4)\le 3$ by Theorem 1.1(1), $d(P_4\square P_4)\gamma (P_4\square P_4)\le 12<16=\left|V(P_4\square P_4)\right|$. Thus, $P_4\square P_4$ is not domatically perfect. □

So far, we have not yet found a pair of two domatically perfect connected graphs of large order such that the Cartesian product of the pair is not domatically perfect. Thus, we conclude this section with proposing the following conjecture.

Conjecture 3.1

Let $G$ and $H$ be domatically perfect connected graphs. Then $G\square H$ is domatically perfect, unless $G\square H$ is either $P_2\square P_4$ or $P_4\square P_4$ .

4 Domatically complete

In general, there is no inclusion relation for two properties, domatically full and domatically perfect. For example, let us consider the graph $G_1=P_2\square P_n$ and $G_2=P_2\square K_n$ for $n\ge 3$. By Theorem 3.4, if $n⁄\equiv 0(mod3)$, then $G_1$ is not domatically perfect, but since $d\left(G_1\right)=3=\delta \left(G_1\right)+1$ [6], $G_1$ is domatically full. On the other hand, $G_2$ is domatically perfect by Theorem 3.1 (or Proposition 3.1), however, it is not domatically full since $\delta \left(G_2\right)+1=n+1>n=d\left(G_2\right)(=2n∕\gamma \left(G_2\right))$.

So we focus on graphs which are domatically full and domatically perfect. In particular, we consider regular graphs satisfying the property.

Definition 4.1

A graph is domatically complete if it is domatically full and domatically perfect.

Proposition 4.1

Let $G$ be a domatically complete $k$ -regular graph of order $n$ , and let $S$ be a $\gamma$ -set of $G$ . Then the following hold:

(i)	$\left|V(G-S)\right|=k\gamma \left(G\right)$ .
(ii)	$S$ is an independent set.
(iii)	For any two vertices $u$ and $v$ in $S$ , $N_G\left(u\right)\cap N_G\left(v\right)=0̸$ .

Proof

(i) Since $d\left(G\right)=n∕\gamma \left(G\right)=\delta \left(G\right)+1=k+1$ by the assumption, $\left|V(G-S)\right|=n-\frac{n}{k+1}=k\gamma \left(G\right)$.

(ii) If $S$ is not independent, then $\left|N_G\left(S\right)\right|<k\gamma \left(G\right)=\left|V(G-S)\right|$, contradicts that $S$ is a dominating set.

(iii) Otherwise, there is a vertex in $G-S$ which is not adjacent to a vertex in $S$ by (i), a contradiction. □

Lemma 4.1

Let $G$ be a domatically complete $k$ -regular graph of order $n$ , and let $S$ be a $\gamma$ -set of $G$ . Then $G-S$ is a domatically complete $(k-1)$ -regular graph.

Proof

By Proposition 4.1(iii), $G-S$ is $(k-1)$-regular. Moreover, $\gamma (G-S)=\gamma \left(G\right)$ since otherwise, i.e., if $\gamma (G-S)<\gamma \left(G\right)$, then for a minimum dominating set $S^{\prime }$ of $G-S$, $\left|N_{G-S}\left(S^{\prime }\right)\right|>k\gamma \left(G\right)-\gamma \left(G\right)=\gamma \left(G\right)(k-1)$. (Note that $\gamma (G-S)>\gamma \left(G\right)$ does not hold since $G-S$ also contains a $\gamma$-set of $G$.) This means that a vertex in $S^{\prime }$ has degree at least $k$ in $G-S$, a contradiction. Thus, $\gamma$-sets of $G$ except $S$ are also minimum dominating sets of $G-S$. Therefore, since $d(G-S)=d\left(G\right)-1=k=k\gamma \left(G\right)∕\gamma (G-S)$, $G-S$ is domatically complete. □

A uniform planting is an operation to make a $k$-regular graph $G$ of order $(k+1)n$ from $(k-1)$-regular graph $H$ of order $kn$, as follows.

1.	We add $n$ vertices $v_0,v_1,\dots ,v_{n-1}$ to $H$, i.e., $V\left(G\right)=V\left(H\right)\cup \{v_0,v_1,\dots ,v_{n-1}\}$.
2.	For each $i\in \{0,1,\dots ,n-1\}$, join $v_i$ to $k$ vertices of $H$ so that $N_G\left(v_i\right)\cap N_G\left(v_j\right)=0̸$ for $i\ne j$.

A uniformly regular $k$ -tree $G_k\left(n\right)$ of a graph is obtained from $G_0\left(n\right)=\overline{K_n}$, where $\overline{K_n}$ is a graph of order $n$ having no edge (i.e., a set of isolated vertices), by repeatedly applying uniform plantings $k$ times.

Theorem 4.1

Every domatically complete $k$ -regular graph $G$ with $k\ge 0$ is isomorphic to a uniformly regular $k$ -tree. Furthermore, $\left|V\left(G\right)\right|=\gamma \left(G\right)(k+1)$ .

Proof

Let $G$ be a domatically complete $k$-regular graph. When $k=0$, i.e., the graph consists only isolated vertices, the theorem holds. If $k\ge 1$, then by Lemma 4.1, we obtain a smaller domatically complete $(k-1)$-regular graph $H$ from $G$ by removing a $\gamma$-set $S$ of $G$. By induction, $H$ is a uniformly regular $(k-1)$-tree. Since $S$ is an independent set and every two vertices in $S$ have no common neighbor by Proposition 4.1(ii) and (iii), $G$ is a uniformly regular $k$-tree obtained from $H$ by a uniform planting. Moreover, by Proposition 4.1(i), we immediately have $\left|V\left(G\right)\right|=\gamma \left(G\right)(k+1)$. □

Theorem 4.1 produces many observations and corollaries. We introduce several representative corollaries among them.

Observation 4.1

If a domatically complete $k$ -regular graph is disconnected, then each component is a uniformly regular $k$ -tree.

Corollary 4.1

Every domatically complete $2$ -regular graph is a union of cycles of length $m\equiv 0(mod3)$ .

Corollary 4.2

There exists a domatically complete $k$ -regular graph with a Hamiltonian cycle.

5 Concluding remarks and open problems

In Section 3, we investigate the conditions for a graph to be domatically perfect. In particular, we study the Cartesian product of several pairs of complete graphs, paths and cycles. Chang [6] studies a pair of graphs such that the Cartesian product of them is domatically full. In the end of his paper, it is conjectured that all $r$-dimensional grids $P_{n_1}\square P_{n_2}\square \cdots \square P_{n_r}$ are domatically full, with finitely many exceptions. In fact, he notes that $d(P_2\square P_2)=d(P_2\square P_4)=2$ though $\delta (P_2\square P_2)=\delta (P_2\square P_4)=2$. On the other hand, the same statement does not hold for domatically perfect by Theorem 3.4, and so, it is an open problem to find a condition for $r$-dimensional grids to be domatically perfect.

Problem 5.1

Find the necessary and sufficient condition for $r$-dimensional grids with $r\ge 3$ to be domatically perfect.

In general, it seems to be difficult to characterize domatically perfect graphs $G$ with $\gamma \left(G\right)\ge 2$. For example, consider the graph $H_1$ (resp., $H_2$) obtained from the complete bipartite graph $K_{n,n}$ with $n\ge 4$ by removing (resp., adding) exactly one edge. It is easy to check that $\gamma \left(H_1\right)=\gamma \left(H_2\right)=\gamma \left(K_{n,n}\right)=2$ and $d\left(H_1\right)=d\left(H_2\right)=d\left(K_{n,n}\right)=n$, that is, all graphs are domatically perfect. So, the characterization of domatically perfect graphs with small domination number is a challenging problem in study on domatically perfect.

Problem 5.2

Characterize domatically perfect graphs with domination number $2$.

In Section 4, we give a characterization of domatically complete regular graphs. However, the characterization is a little flexible. In fact, the theorem allows a domatically complete regular graph to be disconnected; for example, a union complete graph of the same order is also a domatically complete regular graph. So one can try to characterize domatically complete regular graphs with a specified sub-structure; for instance, a Hamiltonian cycle, a perfect matching and so on.

As also introduced in Section 2, Rall [19] discovers a relation between domatically $k$-critical and domatically full, and we described a relation between domatically $k$-critical and domatically perfect in this paper. From these studies, it also seems to be a worthwhile future work to discover some relation between domatically critical and domatically complete.