In a graph G with δ(G)≥k≥1, a k-tuple total restrained dominating set S is a subset of V(G) such that each vertex of V(G) is adjacent to at least k vertices of S and also each vertex of V(G)−S is adjacent to at least k vertices of V(G)−S. The minimum number of vertices of such sets in G is the k-tuple total restrained domination number of G. In [k-tuple total restrained domination/domatic in graphs, BIMS], the author initiated the study of the k-tuple total restrained domination number in graphs. In this paper, we continue it in the complementary prism of a graph.

1. Introduction

Let G be a simple graph with the vertex setV=V(G) and the edge set E=E(G). The order|V| and size|E| of G are denoted by n=n(G) and m=m(G), respectively. The open neighborhood and the closed neighborhood of a vertex v∈V are NG(v)={u∈V∣uv∈E} and NG[v]=NG(v)∪{v}, respectively. Also the open neighborhood and the closed neighborhood of a subset X⊆V(G) are NG(X)=∪v∈XNG(v) and NG[X]=NG(X)∪X, respectively. The degree of a vertex v∈V is deg(v)=|N(v)|. The minimum and maximum degree of a graph G are denoted by δ=δ(G) and Δ=Δ(G), respectively. If every vertex of G has degree k, then G is called k-regular. We write Kn, Cn, and Pn for a complete graph, a cycle and a path of order n, respectively, while Kn1,…,np denotes a complete p-partite graph. The complement of a graph G is denoted by G¯ and is a graph with the vertex set V(G) and for every two vertices v and w, vw∈E(G¯) if and only if vw∉E(G).

For each integer k≥1, the k-joinG∘kH of a graph G to a graph H of order at least k is the graph obtained from the disjoint union of G and H by joining each vertex of G to at least k vertices of H [1]. Also, G∘*kH denotes the k-join G∘kH such that each vertex of G is joined to exact k vertices of H.

The complementary prismGG¯ of G is the graph formed from the disjoint union G∪G¯ of G and G¯ by adding the edges of a perfect matching between the corresponding vertices (same label) of G and G¯ [2]. For example, the graph C5C5¯ is the Petersen graph. Also, if G=Kn, the graph KnKn¯ is the corona Kn∘K1, where the coronaG∘K1 of a graph G is the graph obtained from G by attaching a pendant edge to each vertex of G.

The research of domination in graphs is an evergreen area of graph theory. Its basic concept is the dominating set. The literature on this subject has been surveyed and detailed in the two books by Haynes et al. [3, 4]. And many variants of the dominating set were introduced and the corresponding numerical invariants were defined for them. For example, the k-tuple total dominating set is defined in [1] by Henning and Kazemi, which is an extension of the total dominating set (for more information see [5, 6]).

Definition 1 (see [<xref ref-type="bibr" rid="B6">1</xref>]).

Let k≥1 be an integer and let G be a graph with δ(G)≥k. A subset S⊆V(G) is called a k-tuple total dominating set, briefly kTDS, in G, if for each x∈V(G), |N(x)∩S|≥k. The minimum number of vertices of a k-tuple total dominating set in a graph G is called the k-tuple total domination number of G and denoted by γ×k,t(G).

A numerical invariant of a graph which is in a certain sense dual to it is the domatic number of a graph. The domatic number d(G) and the total domatic number dt(G) of a graph were introduced in [7, 8], respectively. Sheikholeslami and Volkmann extended the last definition to the k-tuple total domatic number d×k,t(G) in [9] and Kazemi extended it to the star k-tuple total domatic number d×k,t*(G) in [10].

Definition 2.

The k-tuple total domatic partition, briefly kTDP, of G is a partition 𝔻 of the vertex set of G such that all classes of 𝔻 are k-tuple total dominating sets in G. The maximum number of classes of a k-tuple total domatic partition of G is called the k-tuple total domatic number d×k,t(G) of G [9]. The stark-tuple total domatic numberd×k,t*(G) of G is the maximum number of classes of a kTDP of G such that at least one of the k-tuple total dominating sets in it has cardinality γ×k,t(G) [10].

The author in [10] initiated the study of the k-tuple total restrained domination number and the k-tuple total restrained domatic number of graphs.

Definition 3 (see [<xref ref-type="bibr" rid="B9">10</xref>]).

The k-tuple total restrained domatic partition, briefly kTRDP, of G is a partition 𝔻 of the vertex set of G such that all classes of 𝔻 are k-tuple total restrained dominating sets in G. The maximum number of classes of a k-tuple total restrained domatic partition of G is the k-tuple total restrained domatic numberd×k,tr(G) of G. Similarly, the stark-tuple total restrained domatic numberd×k,tr*(G) of G is the maximum number of classes of a kTRDP of G such that at least one of the k-tuple total restrained dominating sets in it has cardinality γ×k,tr(G).

In this paper, we continue our studies, which is initiated in [10] and find some sharp bounds for the k-tuple total restrained domination number of the complementary prism of a graph. Also we will find the k-tuple total restrained domination number of a cycle, a path, and a complete multipartite graph.

Through this paper, k is a positive integer, and for simplicity, we assume that V(GG¯) is the disjoint union V(G)∪V(G¯) with V(G¯)={v¯∣v∈V(G)} and E(GG¯)=E(G)∪E(G¯)∪{vv¯∣v∈V(G)} such that E(G¯)={u¯v¯∣uv∉E(G)}. The vertices v and v- are called corresponding vertices. Also for a subset X⊆V(G), we show its corresponding subset in G¯ by X¯. Also we assume that V(Cn)=V(Pn)={i∣1≤i≤n}, V(Cn¯)=V(Pn¯)={i¯∣1≤i≤n}, E(Cn)=E(Pn)∪{1n}={ij∣1≤i≤n-1, and j=i+1}∪{1n}.

The next known results are useful for our investigations.

Proposition 4 (see Henning and Kazemi [<xref ref-type="bibr" rid="B6">1</xref>] 2010).

Let p≥2 be an integer and let G=Kn1,n2,…,np be a complete p-partite graph with n1≤n2≤⋯≤np.

If k<p, then γ×k,t(G)=k+1.

If k=p and ∑i=1k-1ni≥k, then γ×k,t(G)=k+2.

If 2≤p<k and ⌈k/(p-1)⌉≤n1≤n2≤⋯≤np, then γ×k,t(G)=⌈kp/(p-1)⌉.

Proposition 5 (see Kazemi [<xref ref-type="bibr" rid="B8">6</xref>] 2011).

Let n≥4. Then
(1)γt(PnPn¯)={2⌈n-24⌉+1ifn≡3(mod4),2⌈n-24⌉+2otherwise.

Proposition 6 (see Kazemi [<xref ref-type="bibr" rid="B8">6</xref>] 2011).

Let n≥4. Then
(2)γt(CnCn¯)={2⌈n4⌉+2ifn≡0(mod4),2⌈n4⌉+1ifn≡3(mod4),2⌈n4⌉otherwise.

Proposition 7 (see Kazemi [<xref ref-type="bibr" rid="B8">6</xref>] 2011).

If n ≥ 5, then γ×2,t(CnCn¯)=n+2.

Proposition 8 (see Kazemi [<xref ref-type="bibr" rid="B8">6</xref>] 2011).

Let G=Kn1,n2,…,np be a complete p-partite graph with V(GG¯)=⋃1≤i≤p(Xi∪Xi¯), when for each i, Xi is isomorph to Kni¯. If S is a kTDS of GG¯, then for each 1≤i≤p, |S∩Xi¯|≥k. Furthermore, if |S∩Xi¯|=k for some i, then |S∩Xi|≥k.

Proposition 9 (see Kazemi [<xref ref-type="bibr" rid="B8">6</xref>] 2011).

Let G=Kn1,n2,…,np be a complete p-partite graph with 1≤n1≤n2≤⋯≤np. Then
(3)γt(GG¯)=2p-α,
where α=|{i∣1≤i≤p, and ni=1}|.

Proposition 10 (see Kazemi [<xref ref-type="bibr" rid="B8">6</xref>] 2011).

Let G=Kn1,n2,…,np be a complete p-partite graph with 3≤n1≤n2≤⋯≤np. Then γ×2,t(GG¯)=3p+2.

Proposition 11 (see Kazemi [<xref ref-type="bibr" rid="B8">6</xref>] 2011).

Let G=Kn1,n2,…,np be a complete p-partite graph with 5≤k+2≤n1≤⋯≤np. Then
(4)γ×k,t(GG¯)={(p+1)(k+1)ifp≥k+1,(p+1)(k+1)+1ifp=k≥4,16ifp=k=3,p(k+1)+min{2k-2,⌈kpp-1⌉}ifp<k.

Proposition 12 (see Kazemi [<xref ref-type="bibr" rid="B9">10</xref>] 2011).

Let G be a graph of order n in which δ(G)≥k. Then

every vertex of degree at most 2k-1 of G and at least its k neighbors belong to every kTRDS;

d×k,tr(G)=1 if δ(G)≤2k-1;

Δ(G)≥2k if γ×k,tr(G)<n. Hence, n≥2k+2;

γ×k,t(G)≤γ×k,tr(G), and so d×k,tr(G)≤d×k,t(G).

Proposition 13 (see Kazemi [<xref ref-type="bibr" rid="B9">10</xref>] 2011).

Let G be a graph with minimum degree at least k. If d×k,t*(G)≥2, then γ×k,tr(G)=γ×k,t(G).

Proposition 14 (see Kazemi [<xref ref-type="bibr" rid="B9">10</xref>] 2011).

Let n≥k+3≥4. Then
(5)γ×k,tr(Cn¯)={nifn≤2k+2,k+2if2k+3≤n≤3k+2,k+1ifn≥3k+3.

Proposition 15 (see Kazemi [<xref ref-type="bibr" rid="B9">10</xref>] 2011).

Let k<n be positive integers. Then
(6)γ×k,tr(Kn)={nifn≤2k+1,k+1otherwise.

Proposition 16 (see Kazemi [<xref ref-type="bibr" rid="B9">10</xref>] 2011).

Let n≥4. Then
(7)γtr(Cn)={2⌈n4⌉-1ifn≡1(mod4),2⌈n4⌉+1ifn≡3(mod4),2⌈n4⌉otherwise.

2. Some Bounds

We first give a sharp lower bound for the k-tuple total restrained domination number of a regular graph.

Theorem 17.

Let k and ℓ be integers such that 1≤k-1≤ℓ≤2k-2. If G is a ℓ-regular graph of order n, then
(8)γ×k,tr(GG¯)≥n+k,
with equality if and only if n≥ℓ+2k and V(G¯) contains a k-subset T such that for each vertex i¯∈V(G¯), |N(i¯)∩T|≥k-1 and also if i¯∈V(G¯)-T, then |N(i¯)∩(V(G¯)-T)|≥k.

Proof.

Let V(GG¯)=V(G)∪V(G¯) such that V(G)={i∣1≤i≤n} and V(G¯)={i¯∣1≤i≤n}. Let n≥2k+ℓ, and let S be an arbitrary kTRDS of GG¯. Then Proposition 12(i) and this fact that every vertex i∈V(G) has degree ℓ+1≤2k-1 imply that V(G)⊆S. Let i¯∉S. Then |N(i¯)∩V(G¯)∩S|≥k-1. If |N(i¯)∩V(G¯)∩S|≥k, then we have nothing to prove. Thus, let N(i-)∩V(G-)∩S={jm-∣1≤m≤k-1}. But, this implies that there exists a vertex t¯∈S-{jm¯∣1≤m≤k-1} such that its corresponding vertex t in V(G) is adjacent to some vertex jm, when 1≤m≤k-1. Then |S|≥n+k, and since S was arbitrary, we conclude that γ×k,tr(GG¯)≥n+k.

Obviously, it can be seen that γ×k,tr(GG¯)=n+k if and only if n≥ℓ+2k and V(G¯) contains a k-subset T such that for each vertex i¯∈V(G¯), |N(i¯)∩T|≥k-1 and also if i¯∈V(G¯)-T, then |N(i¯)∩(V(G¯)-T)|≥k.

Theorem 17 and Proposition 12(i) imply the next corollary.

Corollary 18.

Let k and ℓ be integers such that 1≤k-1≤ℓ≤2k-2. If G is a ℓ-regular graph of order n≤ℓ+2k-1, then γ×kr(GG¯)=2n.

The next theorem gives lower and upper bounds for γ×k,tr(GG¯), when G is an arbitrary graph.

Theorem 19.

If G is a graph of order n with k≤min{δ(G),δ(G¯)}, then
(9)γ×(k-1),tr(G)+γ×(k-1),tr(G¯)≤γ×k,tr(GG¯)≤γ×k,tr(G)+γ×k,tr(G¯),
when k≥1 in the upper bound and k≥2 in the lower bound.

Proof.

To prove γ×(k-1),tr(G)+γ×(k-1),tr(G¯)≤γ×k,tr(GG¯), let k≥2 and let D be a kTRDS of GG¯. Since every vertex of V(G) (resp., V(G¯)) is adjacent to only one vertex of V(G¯) (resp., V(G)), we conclude that D∩V(G) is a (k-1) TRDS of G and D∩V(G¯) is a (k-1) TRDS of G¯. Then
(10)γ×(k-1),tr(G)+γ×(k-1),tr(G¯)≤|D∩V(G)|+|D∩V(G¯)|=|D|=γ×k,tr(GG¯).
We now prove that γ×k,tr(GG¯)≤γ×k,tr(G)+γ×k,tr(G¯), when k≥1. Since for every kTRDS S of G and every kTRDS S′ of G¯, the set S∪S′ is a kTRDS of GG¯, we have
(11)γ×k,tr(GG¯)≤γ×k,tr(G)+γ×k,tr(G¯).

In Section 4, we will show that the given bounds in Theorem 19 are sharp.

3. The Complementary Prism of Some Graphs

In this section, we will determine γ×k,tr(GG¯) when G is a cycle, a path, or a complete multipartite graph. First, let G be a cycle.

Proposition 20.

Let n≥4. Then
(12)γ×2,tr(CnCn¯)={2nifn=4,5,n+2ifn≥6.

Proof.

Corollary 18 implies that γ×2,tr(CnCn¯)=2n if n=4,5. Now let n≥6. Proposition 7 with Proposition 12(iv) implies γ×2,tr(CnCn¯)≥n+2. Since also V(Cn)∪{1¯,4¯} is a 2TRDS of CnCn¯, we get γ×2,tr(CnCn¯)=n+2 when n≥6.

To calculate γt(CnCn¯) we need to prove that dt*(CnCn¯)≥2.

Proposition 21.

Let n≥4. Then dt*(CnCn¯)≥2.

Proof.

We prove the proposition in the following four cases.

Case 1 (n≡0(mod4)). For n=4, we set S={1,1¯,2,2¯} and S′={3,3¯,4,4¯}. If n>4, we set S={1,1¯,2,2¯}∪{5+4i,6+4i∣0≤i≤⌈n/4⌉-2} and S′ = {3,3¯,4,4¯}∪{7+4i,8+4i∣0 ≤ i≤⌈n/4⌉-2}.

Case 2(n≡1(mod4)). For n=5, we set S={1,1¯,4,4¯} and S′={2,2¯,5,5¯} and for n=9, we set S = {1,1¯,4,4¯,7,7¯} and S′ = {2,2¯,5,5¯,8,8¯}. If n>9, we set S = {1,1¯,4,4¯,7,7¯}∪{10+4i,11+4i∣0 ≤ i≤⌈n/4⌉-4} and S′={3,3¯,6,6¯,9,9¯}∪{12+4i,13+4i∣0≤i ≤ ⌈n/4⌉-4}.

Case 3(n≡2(mod4)). For n=6, we set S={1,1¯,4,4¯} and S′={2,2¯,5,5¯}. If n>6, we set S={1,1¯,4,4¯}∪{7+4i,8+4i∣0≤i≤⌈n/4⌉-3} and S′={3,3¯,6,6¯}∪{9+4i,10+4i∣0≤i≤⌈n/4⌉-3}.

Case 4(n≡3(mod4)). For n=7, we set S={1,1¯,4,4¯,6¯} and S′={2,2¯,5,5¯,7¯}. If n>7, we set S={1,1¯,4,4¯,n-1¯}∪{7+4i,8+4i∣0≤i≤⌈n/4⌉-3} and S′={2,3,3¯,6,6¯}∪{9+4i,10+4i∣0≤i≤⌈n/4⌉-3}.

Since, in all cases, S and S′ are two disjoint γt(CnCn¯)-sets, we have dt*(CnCn¯)≥2.

By Propositions 6, 13, and 21 we obtain the next result.

Proposition 22.

Let n≥4. Then
(13)γtr(CnCn¯)={2⌈n4⌉+2ifn≡0(mod4),2⌈n4⌉+1ifn≡3(mod4),2⌈n4⌉Otherwise.

Now we continue our work when G is a path.

Proposition 23.

Let n≥4. Then
(14)γtr(PnP¯n)={2⌈n4⌉+2ifn≡0(mod4),2⌈n4⌉+1ifn≡0(mod4),2⌈n4⌉Otherwise.

Proof .

Propositions 5 and 12(iv) imply that
(15)γtr(PnPn¯)≥γt(PnPn¯)={2⌈n-24⌉+1ifn≡0(mod4),2⌈n-24⌉+2otherwise.

Let n≡0(mod4). For n =8, we set S ={1¯,8¯,3,4,5,6} and for n>8 we set
(16)S={1¯,n-6¯,n-5¯,n¯,n-3,n-2}∪{3+4i,4+4i∣0≤i≤⌊n4⌋-3}.

If n≡1,2,3(mod4), then we set S ={1¯,n-2¯,n¯,n −2}∪{3+4i,4+4i∣0≤i≤⌊n/4⌋-2}, S ={1¯,n¯}∪{3+4i,4+4i∣0≤i≤⌊n/4⌋-1}, and S ={1¯,n-1¯,n¯}∪{3+4i,4+4i∣0≤i≤⌊n/4⌋-1}, respectively. Since, in each case, S is a TRDS of PnPn¯ of cardinality γt(PnPn¯), we have completed our proof.

In the next propositions, we calculate γ×k,tr(GG¯) when G is a complete multipartite graph.

Proposition 24.

If G=Kn1,n2,…,np is a complete p-partite graph, then
(17)dt(GG-)=min{ni∣1≤i≤p}.

Proof.

Let V(GG¯)=⋃1≤i≤p(Xi∪Xi¯) and let ℓ=min{ni∣1≤i≤p}. Proposition 8 implies that for every TDS D of GG¯, |D∩Xi¯|≥1 when 1≤i≤p. Hence, dt(GG¯)≤ℓ. Now let D1, D2,… and Dℓ be ℓ disjoint 2p-sets of V(GG¯) such that for every j=1,2,…,ℓ and every i=1,2,…,p, |Dj∩Xi|=|Dj∩Xi¯|=1 and x∈Dj∩Xi if and only if x¯∈Dj∩Xi¯. Since D1, D2, …, and Dℓ are ℓ disjoint γt-sets of GG¯, by Proposition 9, we get dt(GG¯)≥ℓ, and so dt(GG¯)=ℓ.

Proposition 25.

If G=Kn1,…,np is a complete p-partite graph with 2≤n1≤⋯≤np, then γtr(GG¯)=2p.

Proof.

Since obviously dt(GG¯) =dt*(GG¯), we obtain γtr(GG¯)=2p, by Propositions 9, 13, and 24.

Proposition 26.

Let G=Kn1,n2 be a complete bipartite graph with 4≤n1≤n2. Then γ×2,tr(GG¯)=8.

Proof.

Let S be a set of vertices such that for i=1,2, |S∩Xi|=|S∩Xi¯|=2 and x∈S∩Xi if and only if x¯∈S∩Xi¯. Since S is a 2TRDS of GG¯ of cardinality γ×2,t(GG¯), we get γ×2,tr(GG¯)=8, by Propositions 10 and 12(iv).

Proposition 27.

Let G=Kn1,n2,…,np be a complete p-partite graph with 5≤n1≤⋯≤np. Then γ×2,tr(GG¯)=3p+2.

Proof.

Let S be a set of vertices such that for i=1,2, |S∩Xi|=|S∩Xi¯|=2 and x∈S∩Xi if and only if x¯∈S∩Xi¯, and for i=3,…,p, |S∩Xi¯|=3. Obviously S is a γ×2,t(GG¯)-set. It can easily be verified that every vertex in out of S is adjacent to at least two vertices in out of S. Hence, S is a 2TRDS of GG¯ of cardinality γ×2,t(GG¯), and so γ×2,tr(GG¯)=3p+2, by Propositions 10 and 12(iv).

Proposition 28.

Let G =Kn1,n2,n3 be a complete 3-partite graph with 6≤n1≤n2≤n3. Then γ×3,tr(GG¯)=16.

Proof.

Let S be a set of vertices such that |S∩X3¯|=4, and for i=1,2, |S∩Xi|=|S∩Xi¯|=3 such that x∈S∩Xi if and only if x¯∈S∩Xi¯. Since S is a 3TRDS of GG¯ of cardinality γ×3,t(GG¯), we get γ×3,tr(GG¯)=16, by Propositions 11 and 12(iv).

Proposition 29.

Let G=Kn1,n2,…,np be a complete p-partite graph with 7≤2k+1≤n1≤⋯≤np. Then
(18)γ×k,tr(GG¯)={(p+1)(k+1)ifp≥k+1,(p+1)(k+1)+1ifp=k≥4,16ifp=k=3,p(k+1)+min{2k-2,⌈kpp-1⌉}ifp<k.

Proof.

We prove the proposition in the following three cases.

Case 1. (p≥k+1or p=k≥4). Let S be a set of vertices such that S∩V(G) is a γ×k,t(G)-set and for i=1,2,…,p, |S∩Xi¯|=k+1. Obviously, S is a γ×k,t(GG¯)-set. It can easily be verified that every vertex in out of S is adjacent to at least k vertices in out of S. Hence, S is a kTRDS of GG¯ of cardinality γ×k,t(GG¯), and so γ×k,tr(GG¯) is (p+1)(k+1) if p≥k+1 and is (p+1)(k+1)+1 if p=k≥4, by Propositions 11 and 12(iv).

Case 2. (p=k=3). This case is proved in Proposition 28 when 6=2k≤n1≤n2≤n3.

Case 3.(p<k). If min{2k-2,⌈kp/(p-1)⌉}=2k-2, let S be a set of vertices such that for i=1,2, |S∩Xi|=|S∩Xi¯|=k and x∈S∩Xi if and only if x¯∈S∩Xi¯, and for i=3,…,p,|S∩Xi¯|=k+1. If min{2k-2,⌈kp/(p-1)⌉}=⌈kp/(p-1)⌉, let S be a set of vertices such that S∩V(G) is a γ×k,t(G)-set and for i=1,2,…,p, |S∩Xi¯|=k+1. In all cases, obviously S is a γ×k,t(GG¯)-set, and it can easily be verified that every vertex in out of S is adjacent to at least k vertices in out of S. Hence, S is a kTRDS of GG¯ of cardinality γ×k,t(GG¯), and so γ×2,tr(GG¯)=p(k+1)+min{2k-2,⌈kp/(p-1)⌉}, by Propositions 11 and 12(iv).

4. The Given Bounds in Theorem <xref ref-type="statement" rid="thm2.3">19</xref> Are Sharp

In this section, we show that the given bounds in Theorem 19 are sharp. For this aim, we first calculate the k-tuple total restrained domination number of a complete multipartite graph and its complement.

Proposition 30.

Let G=Kn1,n2,…,np be a complete p-partite graph of order n with k+1≤n1≤⋯≤nt≤2k+1<nt+1≤⋯≤np. If p≥k+1, then
(19)γ×k,tr(G¯)=n1+⋯+nt+(p-t)(k+1).

Proof.

Since G¯ is the union of disjoint complete graphs Kn1, Kn2,…, Knp, Proposition 15 implies that
(20)γ×k,tr(G¯)=γ×k,tr(Kn1)+γ×k,tr(Kn2)+⋯γ×k,tr(Knp)=n1+⋯+nt+(p-t)(k+1).

Proposition 31.

Let G=Kn1,n2,…,np be a complete p-partite graph with 2≤n1≤⋯≤np. If p≥k+1, then γ×k,tr(G)=k+1.

Proof.

Let S be a set of vertices of cardinality k+1 such that for every index i=1,2,…,k+1, |S∩Xi|=1. Since S is a kTRDS of G of cardinality γ×k,t(G), Propositions 12(iv) and 4(i) imply that γ×k,tr(G)=k+1.

Proposition 32.

Let G=Kn1,n2,…,nk be a complete k-partite graph of order n with n1≤n2≤⋯≤nk. If n-nk-1≥n-nk≥2k and n-n1≥⋯≥n-nk-2≥2k+1, then γ×k,tr(G)=k+2.

Proof.

Let S be a set of vertices of cardinality k+2 such that |S∩Xi|=2 for i=k-1,k, and |S∩Xi|=1 for i=1,2,…,k-2. Since S is a kTRDS of G of cardinality γ×k,t(G), Propositions 4(ii) and 12(iv) imply that γ×k,tr(G)=k+2.

Proposition 33.

Let G=Kn1,n2,…,np be a complete p-partite graph of order with ⌈k/(p-1)⌉≤n1≤⋯≤np, and let p<k. If p-1∣k and, for each index i=1,2,…,p, we have n-ni≥2k, then γ×k,tr(G)=kp/(p-1).

Proof.

Let S be a set of vertices of cardinality kp/(p-1) such that for each i=1,2,…,p, |S∩Xi|=k/(p-1). Since S is a kTRDS of G of cardinality γ×k,t(G), Propositions 4(iii) and 12(iv) imply that γ×k,tr(G)=kp/(p-1).

Proposition 34.

Let G=Kn1,n2,…,np be a complete p-partite graph of order n with ⌈k/(p-1)⌉≤n1≤⋯≤np, and let p<k. Let also k = (p-1)·⌊k/(p-1)⌋+r for some integer 1≤r≤p-2. If n-np-r ≥ n-np-r+1≥⋯≥n-np ≥ ⌈kp/(p-1)⌉-⌈k/(p-1)⌉+k and n-n1≥⋯≥n-np-r-1 ≥ ⌈kp/(p-1)⌉-⌈k/(p-1)⌉+k+1, then γ×k,tr(G)=⌈kp/(p-1)⌉.

Proof.

Let S be a set of vertices of cardinality 1≤i≤p-r-1, |S∩Xi|=⌊k/(p-1)⌋ and for p-r≤i≤p,|S∩Xi|=⌈k/(p-1)⌉=⌊k/(p-1)⌋+1. Since S is a kTRDS of G of cardinality γ×k,t(G), Propositions 4(iii) and 12(iv) imply that γ×k,tr(G)=⌈kp/(p-1)⌉.

Comparing Propositions 29, 30, 31, 32, 33, and 34 shows that the following two results, which state the given bounds in Theorem 19 are sharp, are proved.

Proposition 35.

For every integer k≥1, let G=Kn1,n2,…,np be a complete p-partite graph of order n with 2k+2≤n1≤n2≤⋯≤np. If either p≥k+1 or p=k≥4 and 2k≤n-nk≤n-nk-1, 2k+1≤n-nk-2≤⋯≤n-n1, then
(21)γ×k,tr(GG¯)=γ×k,tr(G)+γ×k,tr(G¯).

Proposition 36.

Let G=Kn1,n2,…,np be a complete p-partite graph, and let k≥1 be an integer. If k≤n1≤⋯≤nt≤2k-1<nt+1≤⋯≤np and n1+n2+⋯+nt=p+1+tk for some integer t≥1, then
(22)γ×k,tr(GG¯)=γ×(k-1),tr(G)+γ×(k-1),tr(G¯).

We note that there are some complete multipartite graphs that satisfy Proposition 36. For example, if k≥4, then the complete (k+1)-partite graph G=Kn1,n2,…,nk+1 with the conditions n1=k+3, n2=2k-1, and 2k≤n3≤⋯≤nk+1 satisfies it.

Also Propositions 14, 16, and 20 by this fact that γ×2,tr(Cn)=n, which is obtained by Proposition 12(i), imply that
(23)γ×2,tr(CnCn¯)=γ×2,tr(Cn)+γ×k,tr(Cn¯)
if and only if n=5. Also they imply that
(24)γtr(Cn)+γtr(Cn¯)<γ×2,tr(CnCn¯)<γ×2,tr(Cn)+γ×k,tr(Cn¯),
when n≥4 in the lower bound and n≥6 in the upper bound.

5. Open Problem

Finally, we finish our paper with the following problems.

Problem 37.

Characterize graphs G that satisfy γ×k,tr(GG¯)=γ×k,tr(G)+γ×k,tr(G¯).

Problem 38.

Characterize graphs G that satisfy γ×k,tr(GG¯)=γ×(k-1),tr(G)+γ×(k-1),tr(G¯).

HenningM. A.KazemiA. P.k-tuple total domination in graphsHaynesT. W.HenningM. A.SlaterP. J.van der MerweL. C.The complementary product of two graphsHaynesT. W.HedetniemiS. T.SlaterP. J.HaynesT. W.HedetniemiS. T.SlaterP. J.HenningM. A.KazemiA. P.k-tuple total domination in cross products of graphsKazemiA. P.k-tuple total domination in complementary prismsCockayneE. J.HedetniemiS. T.Towards a theory of domination in graphsCockayneE. J.DawesR. M.HedetniemiS. T.Total domination in graphsSheikholeslamiS. M.VolkmannL.The k-tuple total domatic number of a graphsubmitted to. Utilitas Mathematica, http://arxiv.org/abs/1106.5589KazemiA. P.k-tuple total restrained domination/domatic in graphsBulletin of the Iranian Mathematical Sciences, accepted