# k-Tuple Total Domination in Complementary Prisms

Authors: Adel P. Kazemi
Journal: ISRN Discrete Mathematics
 (2011)

---

## Abstract

Letk be a positive integer, and let G be a graph with minimum degree at least k. In their study (2010), Henning and Kazemi defined the k-tuple total domination number γ×k,tG of G as the minimum cardinality of a k-tuple total dominating set of G, which is a vertex set such that every vertex of G is adjacent to at least k vertices in it. If G̅ is the complement of G, the complementary prism GG̅ of G is the graph formed from the disjoint union of G and G̅ by adding the edges of a perfect matching between the corresponding vertices of G and G̅. In this paper, we extend
some of the results of Haynes et al. (2009) for the k-tuple total domination number
and also obtain some other new results. Also we find the k-tuple total domination number of the
complementary prism of a cycle, a path, or a complete multipartite graph.


---

## Body

## 1. Introduction

In this paper,G=(V,E) is a simple graph with the vertex setV and the edge setE. The order|V| of G is denoted by n=n(G). The open neighborhood and the closed neighborhood of a vertex v∈V are NG(v)={u∈V(G)∣uv∈E(G)} and NG[v]=NG(v)∪{v}, respectively. Also the degree of v is degG(v)=|NG(v)|. Similarly, the open neighborhood and the closed neighborhood of a set S⊆V are NG(S)=⋃v∈SN(v) and NG[S]=NG(S)∪S, respectively. The complement of G is the graph G¯ with the vertex set V(G¯)=V(G) and the edge set E(G¯)={uv∣uv∉E(G)}. The minimum and maximum degree of G are denoted by δ=δ(G) and Δ=Δ(G), respectively. We also write Kn, Cn, and Pn for the complete graph, cycle, and path of order n, respectively, while G[S] and Kn1,n2,…,np denote the subgraph induced on G by a vertex set S, and the complete p-partite graph, respectively.Haynes et al. in [1] have defined complementary product of two graphs that generalizes the Cartesian product of two graphs. Let G and H be two graphs. For each R⊆V(G) and S⊆V(H), the complementary productG(R)□H(S) is a graph with the vertex set {(ui,vj)∣ui∈V(G),vi∈V(H)} and (ui,vj)(uh,vk) is an edge in E(G(R)□H(S))(1)
ifi=h, ui∈R, and vjvk∈E(H) or if i=h, ui∉R, and vjvk∉E(H), or(2)
ifj=k, vj∈S, and uiuh∈E(G) or if j=k, vj∉S, and uiuh∉E(G).In other words, for eachui∈V(G), we replace ui by a copy of H if ui is in R and by a copy of its complement H¯ if ui is not in R, and for each vj∈V(H), we replace each vj by a copy of G if vj∈S and by a copy of G¯ if vj∉S. If R=V(G) (resp., S=V(H)), we write simply G□H(S) (resp., G(R)□H). Thus, G□H(S) is the graph obtained by replacing each vertex v of H by a copy of G if v∈S and by a copy of G¯ if v∉S and replacing each vertex u of G by a copy of H. We recall that the Cartesian productG□H of two graphs G and H is the complementary product G(V(G))□H(V(H)). The special complementary product G□K2(S), where |S|=1, is called the complementary prism of G and denoted by GG¯. 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. We notice that δ(GG¯)=min{δ(G),δ(G¯)}+1.In [2], Henning and Kazemi introduced the k-tuple total domination number of graphs. Let k be a positive integer. A subset S of V is a k-tuple total dominating set of G, abbreviated kTDS, if for every vertex v∈V,  |N(v)∩S|≥k, that is, S is a kTDS of G if every vertex of V has at least k neighbors in S. The k-tuple total domination numberγ×k,t(G) of G is the minimum cardinality of a kTDS of G. We remark that a 1-tuple total domination is the well-studied total domination number. Thus, γt(G)=γ×1,t(G). For a graph to have a k-tuple total dominating set, its minimum degree is at least k. Since every (k+1)-tuple total dominating set is also a k-tuple total dominating set, we note that γ×k,t(G)≤γ×(k+1),t(G) for all graphs with minimum degree at least k+1. A kTDS of cardinality γ×k,t(G) is called a γ×k,t(G)-set. When k=2, a 2-tuple total dominating set is called a double total dominating set, abbreviated DTDS, and the 2-tuple total domination number is called the double total domination number. The redundancy involved in k-tuple total domination makes it useful in many applications. The paper in [3] gives more information about the k-tuple total domination number of a graph.In [4], Haynes et al. discussed the domination and total domination number of complementary prisms. In this paper, we extend some of their results for the k-tuple total domination number and obtain some other results. More exactly, we find some useful lower and upper bounds for the k-tuple total domination number of the complementary prism GG¯ in terms on the order of G, γ×k,t(G), γ×k,t(G¯), γ×(k-1),t(G), and γ×(k-1),t(G¯), in which some of the bounds are sharp. Also we find this number for GG¯, when G is a cycle, a path, or a complete multipartite graph.Through of 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 the corresponding vertices. Also for a subset X⊆V(G), we show its corresponding subset in G¯ with X¯. The next known results are useful for our investigations.Proposition A (Haynes et al. [2]).
IfG is a path or a cycle of order n≥5 such that n≡2(mod4) or is the corona graph Kn∘K1, where n≥3, then γt(GG¯)=γt(G).Proposition B (Henning and Kazemi [4]).
Letp≥2 be an integer, and let G=Kn1,n2,…,np be a complete p-partite graph, where n1≤n2≤⋯≤np.(i)
Ifk<p, then γ×k,t(G)=k+1,(ii)
ifk=p and ∑i=1k-1ni≥k, then γ×k,t(G)=k+2,(iii)
if2≤p<k and ⌈k/(p-1)⌉≤n1≤n2≤⋯≤np, then γ×k,t(G)=⌈kp/(p-1)⌉.Proposition C (Henning and Kazemi [5]).
LetG be a graph of order n with δ(G)≥k. Then
(1.1)γ×k,t(G)≥max⁡{k+1,⌈knΔ(G)⌉}.Proposition D (Henning and Kazemi [5]).
LetG be a graph of order n with δ(G)≥k, and let S be a kTDS of G. Then for every vertex v of degree k in G, NG(v)⊆S.


## 2. Some Bounds

The next two theorems state some lower and upper bounds forγ×k,t(GG¯).Theorem 2.1.
IfG is a graph of order n with 2≤k≤min{δ(G),δ(G¯)}, then
(2.1)γ×(k-1),t(G)+γ×(k-1),t(G¯)≤γ×k,t(GG¯)≤min⁡{γ×(k-1),t(G),γ×(k-1),t(G¯)}+n.Proof.
Since for everyγ×(k-1),t(G)-set D the set D∪V(G¯) is a kTDS of GG¯, we get γ×k,t(GG¯)≤γ×(k-1),t(G)+n. Similarly, we have γ×k,t(GG¯)≤γ×(k-1),t(G¯)+n. Therefore
(2.2)γ×k,t(GG¯)≤min⁡{γ×(k-1),t(G),γ×(k-1),t(G¯)}+n.
For provingγ×(k-1),t(G)+γ×(k-1),t(G¯)≤γ×k,t(GG¯), let D be a kTDS of GG¯. Then D∩V(G) is a (k-1)TDS of G and D∩V(G¯) is a (k-1)TDS of G¯. Since every vertex of V(G) (resp., V(G¯)) is adjacent to only one vertex of V(G¯) (resp., V(G)). Therefore
(2.3)γ×(k-1),t(G)+γ×(k-1),t(G¯)≤|D∩V(G)|+|D∩V(G¯)|=|D|=γ×k,t(GG¯).The given bounds in Theorem2.1 are sharp. Let G be a (k-1)-regular graph of odd order n=2k-1. Then G¯ and GG¯ are (k-1)- and k-regular, respectively, and Proposition D implies γ×k,t(GG¯)=2n and γ×(k-1),t(G)=γ×(k-1),t(G¯)=n. Therefore(2.4)γ×(k-1),t(G)+γ×(k-1),t(G¯)=γ×k,t(GG¯)=min⁡{γ×(k-1),t(G),γ×(k-1),t(G¯)}+n.
The Harary graphs H2m,4m+1 [6] are a family of this kind of graphs. We recall that the Harary graph H2m,n is a 2m-regular graph with the vertex set {i∣1≤i≤n} and every vertex i is adjacent to the 2m vertices in the set(2.5){σji∣σji≡i+j(mod⁡n)orσji≡i-j(mod⁡n),for1≤j≤m}.Theorem 2.2.
IfG is a graph of order n with 1≤k≤min{δ(G),δ(G¯)}, then
(2.6)max⁡{γ×k,t(G),γ×k,t(G¯)}≤γ×k,t(GG¯)≤γ×k,t(G)+γ×k,t(G¯),
and the lower bound is sharp for k=1.Proof.
Triviallymax{γ×k,t(G),γ×k,t(G¯)}≤γ×k,t(GG¯). Let S be a kTDS of G, and let S′ be a kTDS of G¯. Then S∪S′ is a kTDS of GG¯, and so
(2.7)γ×k,t(GG¯)≤γ×k,t(G)+γ×k,t(G¯).
Proposition A implies that, if k=1, then the lower bound is sharp for all paths and cycles of order n≥5, where n≡2(mod4), and for the corona graph Kn∘K1, where n≥3.In special casek=1, we get the following result in [1].Corollary 2.3 (see [1]).
IfG and G¯ have no isolated vertices, then
(2.8)max⁡{γt(G),γt(G¯)}≤γt(GG¯)≤γt(G)+γt(G¯).


## 3. The Complementary Prism of Some Graphs

In this section, we calculate thek-tuple total domination number of the complementary prism GG¯, when G is a complete multipartite graph, a cycle, or a path. First let G=Kn1,n2,…,np be a complete p-partite graph with the vertex partition V(G)=X1∪X2∪⋯∪Xp such that for each 1≤i≤p, |Xi|=ni and n1≤n2≤⋯≤np. Then V(GG¯)=⋃1≤i≤p(Xi∪Xi¯), where Xi¯ denotes the corresponding set of Xi. Trivially for GG¯ to have k-tuple total domination number we should have k≤n1≤n2≤⋯≤np. In the next five propositions, we calculate this number for the complementary prism of the complete p-partite graph G. First we state the following key lemma which has an easy proof that is left to the reader.Lemma 3.1.
LetG=Kn1,n2,…,np be a complete p-partite graph with V(GG¯)=⋃1≤i≤p(Xi∪Xi¯). 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 3.2.
LetG=Kn1,n2,…,np be a complete p-partite graph with 1≤n1≤n2≤⋯≤np. Then
(3.1)γt(GG¯)=2p-α,
where α=|{i∣1≤i≤p, and ni=1}|.Proof.
LetS be an arbitrary kTDS of GG¯, and let n1=n2=⋯=nα=1<nα+1≤⋯≤np. Proposition D implies that for every 1≤i≤p, |S∩Xi¯|≥2 or |S∩Xi¯|=1 and |S∩Xi|≥1. Also if |Xi¯|=1 and |S∩Xi¯|=0, it implies |S∩Xi|=1. Therefore |S|≥α+2(p-α)=2p-α, and hence γt(GG¯)≥2p-α. Now we set A as a p-set such that |A∩Xi|=1, for each 1≤i≤p. Since A∪{xi¯∣xi∈Aandα+1≤i≤p} is a TDS of G of cardinality 2p-α, we get γt(GG¯)=2p-α.Corollary 3.3 (see [1]).
Ifn≥2, then γt(KnKn¯)=n.Proposition 3.4.
IfG=Kn1,n2,…,np is a complete p-partite graph with 2≤k=n1=⋯=nα<nα+1≤⋯≤np, then
(3.2)γ×k,t(GG¯)={p(k+1)+2k-2ifα=1,p(k+1)+α(k-1)otherwise.Proof.
We discussα.
Case 1 (α≥2).
It follows byα≥2 and Lemma 3.1 that, for every k-tuple total dominating set S of GG¯, |S∩Xi|≥|S∩Xi¯|=k for 1≤i≤α and |S∩Xi¯|≥k+1 for α+1≤i≤p. Then
(3.3)γ×k,t(GG¯)≥p(k+1)+α(k-1).
Now we set D=(⋃1≤i≤α(Xi∪Xi¯))∪(⋃α+1≤i≤pDi¯) such that Di¯ is a (k+1)-subset of Xi¯, for α+1≤i≤p. Since D is a kTDS of GG¯ of cardinality p(k+1)+α(k-1), we have γ×k,t(GG¯)=p(k+1)+α(k-1).Case 2 (α=1).
It follows byα=1 and Lemma 3.1 that, for every kTDS S of GG¯, X1∪X1¯ is a subset of S and also every vertex of X1¯∪X2∪⋯∪Xp is adjacent to at least k vertices of S∩(X1¯∪X1). Thus either |S∩Xi¯|=k+1 for each 2≤i≤p and ∑2≤i≤p|S∩Xi|≥k-1 or
(3.4)|S∩X2¯|=⋯=|S∩Xβ¯|=k,|S∩Xβ+1¯|=⋯=|S∩Xp¯|=k+1,
for some 2≤β≤p. Therefore
(3.5)|S|≥min⁡{2k+(k-1)+(p-1)(k+1),2k+2(β-1)k+(p-β)(k+1)}=p(k+1)+2(k-1).
Now we set D=(X1∪X1¯)∪(⋃2≤i≤pDi¯)∪D0 such that Di¯ is a (k+1)-subset of Xi¯ for 2≤i≤p and D0 is a (k-1)-subset of V(G) such that |D0∩X2|=⋯=|D0∩Xk|=1. Since D is a kTDS of GG¯ of cardinality p(k+1)+2k-2, we get γ×k,t(GG¯)=p(k+1)+2k-2.Now letG=Kn1,n2,...,np be a complete p-partite graph with 3≤k+1=n1=⋯=nα<nα+1≤⋯≤np, and let S be a minimal kTDS of GG¯. Then |S∩Xi¯|≥k, by Lemma 3.1. We notice that if |S∩Xi¯|≥k+2, for some i, then we may improve S and obtain another kTDS S′ of cardinality |S| such that |S′∩Xi¯|=k+1 (since every vertex in Xi¯ (respectively Xi) is adjacent to only one vertex in Xi (respectively Xi¯)). Therefore, we may assume that for every minimal kTDS S of GG¯, we have k≤|S∩Xi¯|≤k+1.Now letS be a minimal kTDS of GG¯, and let B={i|1≤i≤p,|S∩Xi¯|=k} be a set of cardinality β. We consider the following two cases.Case 1 (β≠0).
In this case, ifi∈B, we have |S∩Xi¯|=|S∩Xi|=k such that x∈S∩Xi if and only if x¯∈S∩Xi¯, and |S∩Xi¯|=k+1 otherwise. If β≥2, then
(3.6)|S|=p(k+1)+β(k-1),
and if β=1 and B={i}, then we have also |S∩(V(G)-Xi)|=k. Hence
(3.7)|S|=p(k+1)+2k-1.
Comparing (3.6), (3.7) shows that for β≠0 if S is a set of vertices such that S∩Xi={xji∣1≤j≤k} and S∩Xi¯={xji¯∣xji∈S∩Xi} for i=1,2 and |S∩Xi¯|=k+1 for 3≤i≤p, then S is a minimum kTDS of GG¯ and
(3.8)|S|=p(k+1)+2k-2.Case 2 (β=0).
In this case, for each1≤i≤p we have |S∩Xi¯|=k+1. We continue our discussion in the next subcases.
Subcase 1 (α≥k+1 or α=k≤p).
Then obviously|S∩V(G)|≥k. If for 1≤i≤k we consider |S∩Xi|=1, then S is a minimum kTDS of GG¯ and
(3.9)|S|=p(k+1)+k.Subcase 2 (α<k≤p).
Then obviously|S∩V(G)|≥k+1. If we set S such that |S∩X1|=2, and |S∩Xi|=1 when 2≤i≤k, then S is a minimum kTDS of GG¯ and
(3.10)|S|=p(k+1)+k.Subcase 3 (α=p≤k-1).
Then obviously|S∩V(G)|≥γ×(k-1),t(G). If S∩V(G) is a γ×(k-1),t(G)-set, then S is a minimum kTDS of GG¯, and Proposition B implies
(3.11)|S|={(p+1)(k+1)ifα=p=k-1,p(k+1)+⌈(k-1)pp-1⌉ifα=p<k-1.Subcase 4 (α<p<k).
Then obviously|S∩V(G)|≥γ×k,t(G). If S∩V(G) is a γ×k,t(G)-set, then S is a minimum kTDS of GG¯, and Proposition B implies
(3.12)|S|=p(k+1)+⌈kpp-1⌉.Now letG=Kn1,n2,...,np be a complete p-partite graph with 4≤k+2≤n1≤n2≤⋯≤np, and let S is a minimal kTDS of GG¯. In this case, we may similarly assume that k≤|S∩Xi¯|≤k+1. Also it can be easily seen that if |S∩Xi¯|=k for some i, then equality (3.8) holds. Thus let {i∣1≤i≤p,|S∩Xi¯|=k}=∅. Then obviously |S∩V(G)|≥γ×k,t(G). If we choose a set S such that S∩V(G) is a γ×k,t(G)-set and |S∩Xi¯|=k+1 for 1≤i≤p, then S is a minimum kTDS of GG¯, and Proposition B implies (3.13)|S|={(p+1)(k+1)ifp≥k+1,(p+1)(k+1)+1ifp=k,p(k+1)+⌈kpp-1⌉ifp<k.
Comparing (3.9), (3.10), (3.11), (3.12), and (3.13) with (3.8) shows that we have proved the following propositions.Proposition 3.5.
LetG=Kn1,n2,...,np be a complete p-partite graph with 3≤n1≤n2≤⋯≤np.  Then γ×2,t(GG¯)=3p+2.Proposition 3.6.
LetG=Kn1,n2,...,np be a complete p-partite graph with 4≤k+1=n1=⋯=nα<nα+1≤⋯≤np. Then
(3.14)γ×k,t(GG¯)={p(k+1)+kifα=k≤porα≥k+1(p+1)(k+1)ifα<k≤porα=p=k-1,p(k+1)+min⁡{2k-2,⌈(k-1)pp-1⌉}ifα=p<k-1,p(k+1)+min⁡{2k-2,⌈kpp-1⌉}ifα<p<k.Proposition 3.7.
LetG=Kn1,n2,...,np be a complete p-partite graph with 5≤k+2≤n1≤⋯≤np.  Then
(3.15)γ×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.We now determine thek-tuple total domination number of the complementary prism CnCn¯, where 1≤k≤3=δ(CnCn¯). Here we assume that V(CnCn¯)=V(Cn)∪V(Cn¯), V(Cn)={i∣1≤i≤n}, and E(Cn)={(i,i+1)∣1≤i≤n}. Proposition D implies that γ×3,t(CnCn¯)=2n. In many references, for example, in [1], it can be seen that, for n≥3,(3.16)γt(Cn)={2⌈n4⌉ifn≢1(mod⁡4),2⌈n4⌉-1ifn≡1(mod⁡4),
and trivially we can prove(3.17)γt(Cn¯)={4ifn=4,3ifn=5,2ifn≥6.
Hence Theorem 2.1 implies that(3.18)γt(Cn)+2≤γ×2,t(CnCn¯)≤n+2,
where n≥6, and also Theorem 2.2 implies that(3.19)n≤γ×2,t(CnCn¯)≤n+γ×2,t(Cn¯),
where n≥5. In chain (3.19) we need to calculate γ×2,t(Cn¯), which is done by the next proposition.Proposition 3.8.
IfCn is a cycle of order n≥5, then
(3.20)γ×2,t(Cn¯)={5ifn=5,4if6≤n≤8,3ifn≥9.Proof.
Proposition C implies thatγ×2,t(Cn¯)≥3. If n≥9, then, for each 1≤i≤n, the set {i¯,i+3¯,i+6¯} is a DTDS of Cn¯ and so γ×2,t(Cn¯)=3. If 6≤n≤8, then it can be easily verified that γ×2,t(Cn¯)≥4. Now since {1¯,3¯,4¯,6¯} and {1¯,2¯,4¯,6¯} are double total dominating sets of Cn¯, where n=6 and n=7,8, respectively, we get γ×2,t(Cn¯)=4. Finally if n=5, then C5¯ is 2-regular and Proposition D implies γ×2,t(C5¯)=5.Proposition 3.9.
Ifn≥5, then γ×2,t(CnCn¯)=n+2.Proof.
Letn≥5. equalities (3.18), (3.19) and Propositions C and 3.8 imply
(3.21)max⁡{n,⌈4nn-2⌉}≤γ×2,t(CnCn¯)≤n+2.
If n=5, then max{n,⌈4n/(n-2)⌉}=⌈4n/(n-2)⌉=7=n+2, and so γ×2,t(CnCn¯)=n+2. Thus we assume n≥6. Then max{n,⌈4n/(n-2)⌉}=n and hence n≤γ×2,t(CnCn¯)≤n+2. Now let S be a γ×2,t(CnCn¯)-set. If V(Cn)⊆S, then S=V(Cn)∪{x¯,y¯}, for some two adjacent vertices x¯,y¯∈V(Cn¯), and so γ×2,t(CnCn¯)=n+2. Thus we assume V(Cn)⊈S. Without loss of generality, let 3∉S. Since |S∩{2,4,3¯}|≥2, we continue our proof in the following two cases.Case 1 ({2,4}⊆S).
Then1,5,2¯,4¯∈S. We note that, for every 5≤i≤n-1, S∩{i¯,i+1}≠∅. This implies |S|≥(n-1-4)+6=n+1, and since 3¯ must be dominated by S∩V(Cn¯), we have |S∩V(Cn¯)|≥4. If n∉S, then 1¯∈S and so |S|≥n+1+|{1¯}|=n+2. Let n∈S. If n¯∈S, again |S|≥n+1+|{n¯}|=n+2. But n¯∉S implies n-1∈S. Let ß={i∈S∣5≤i≤n-1andi¯∈S}. The condition |S∩V(Cn¯)|≥4 implies |ß|≥2. Therefore for at least one vertex 5≤x≤n-1, {x¯,x+1}⊆S and hence |S|≥n+|{x¯,x+1}|=n+2.Case 2 ({4,3¯}⊆S (similarly {2,3¯}⊆S)).
Case1 implies 2∉S. Then 1¯,2¯,4¯,1,4,5∈S. Again we see that, for every 5≤i≤n-2, S∩{i¯,i+1}≠∅ and so |S|≥(n-2-4)+8=n+2.Therefore, in the previous all cases, we proved that γ×2,t(CnCn¯)≥n+2 and chain (3.21) implies γ×2,t(CnCn¯)=n+2.Corollary 3.10.
Ifn≥5, then
(3.22)γ×2,t(CnCn¯)={γ×2,t(Cn)+γ×2,t(Cn¯)-1ifn≥9,γ×2,t(Cn)+γ×2,t(Cn¯)-2if6≤n≤8,γ×2,t(Cn)+γ×2,t(Cn¯)-3ifn=5.Now we determine the exact amount ofγt(CnCn¯) for n≥3. Obviously γt(C3C3¯)=|V(C3)|=3. In the next proposition we calculate it when n≥4.Proposition 3.11.
Letn≥4. Then
(3.23)γt(CnCn¯)={2⌈n4⌉+2ifn≡0(mod⁡4),2⌈n4⌉+1ifn≡3(mod⁡4),2⌈n4⌉otherwise.Proof.
Theorem2.2 with equalities (3.16) and (3.17) implies
(3.24)4≤γt(C4C4¯)≤6,4≤γt(C5C5¯)≤8,
and if n≥6 and n≢1(mod4), then
(3.25)2⌈n4⌉≤γt(CnCn¯)≤2⌈n4⌉+2,
and if n≥6 and n≡1(mod4), then
(3.26)2⌈n4⌉-1≤γt(CnCn¯)≤2⌈n4⌉+1.
If n=4 and n=5, then the sets {1,2,1¯,2¯} and {1,1¯,4,4¯} are total dominating sets of CnCn¯, respectively. Hence chain (3.24) implies γt(CnCn¯)=4 for n=4,5. Now we assume n≥6. For n≡2(mod4), since the sets {1,1¯,4,4¯} and {1,1¯,4,4¯}∪{7+4i,8+4i∣0≤i≤⌈n/4⌉-3} are two total dominating sets of CnCn¯ of cardinality 2⌈n/4⌉, where n=6 and n>6, respectively, we have γt(CnCn¯)=2⌈n/4⌉, by chain (3.25). Now let n≢2(mod4). We assume that S is a TDS of CnCn¯. Obviously S∩V(Cn¯)≠∅. If |S∩V(Cn¯)|=1 and S∩V(Cn¯)={1¯}, then 1,2,n∈S, and hence |S∩X|≥2⌈|X|/4⌉=2⌈(n-5)/4⌉, where X=V(Cn)-{1,2,3,n-1,n}. This implies
(3.27)|S|=|S∩X|+4≥{2⌈n4⌉+2ifn≡0(mod⁡4),2⌈n4⌉+1ifn≡3(mod⁡4),2⌈n4⌉ifn≡1(mod⁡4).
Now let |S∩V(Cn¯)|=α≥2. If n≡0,1(mod4), then
(3.28)|S∩V(Cn)|≥{2⌊n-α4⌋ifn≡α(mod⁡4),2⌊n-α4⌋+1otherwise,
and if n≡3(mod4), then
(3.29)|S∩V(Cn)|≥{2⌈n-α4⌉-1ifn≡α+1(mod⁡4),2⌈n-α4⌉otherwise.
It can be calculated that
(3.30)|S|=|S∩V(Cn)|+α≥{2⌈n4⌉+2ifn≡0(mod⁡4),2⌈n4⌉+1ifn≡3(mod⁡4),2⌈n4⌉ifn≡1(mod⁡4).
Then by chains (3.25) and (3.26) we have
(3.31)γt(CnCn¯)=2⌈n4⌉+2ifn≡0(mod⁡4),(3.32)2⌈n4⌉≤γt(CnCn¯)≤2⌈n4⌉+1ifn≡1(mod⁡4),(3.33)2⌈n4⌉+1≤γt(CnCn¯)≤2⌈n4⌉+2ifn≡3(mod⁡4).
If n≡1(mod4), then the sets {1,1¯,4,4¯,7,7¯} and {1,1¯,4,4¯,7,7¯}∪{10+4i,11+4i∣0≤i≤⌈n/4⌉-4} are total dominating sets of CnCn¯ of cardinality 2⌈n/4⌉ when n=9 and n>9, respectively. Hence γt(CnCn¯)=2⌈n/4⌉, by chain (3.32). If also n≡3(mod4), the sets {1,1¯,4,4¯,n-1¯} and {1,1¯,4,4¯,n-1¯}∪{7+4i,8+4i∣0≤i≤⌈n/4⌉-3} are total dominating sets of CnCn¯ of cardinality 2⌈n/4⌉+1 when n=7 and n>7, respectively. Hence γt(CnCn¯)=2⌈n/4⌉+1, by chain (3.33).Finally we determine thek-tuple total domination number of the complementary prism PnPn¯, where 1≤k<2=δ(PnPn¯). We recall that V(PnPn¯)=V(Pn)∪V(Pn¯), V(Pn)={i∣1≤i≤n}, and E(Pn)={ij∣1≤i≤n-1,j=i+1}. In many references, for example, in [1], it can be seen that, for n≥2,(3.34)γt(Pn)={2⌈n4⌉ifn≢1(mod⁡4),2⌈n4⌉-1ifn≡1(mod⁡4),
and trivially γt(Pn¯)=|{1¯,n¯}|=2, where n≥4. Therefore, by Theorems 2.1 and 2.2, for n≥4, we have the following chain:(3.35)γt(Pn)≤γt(PnPn¯)≤γt(Pn)+2≤γ×2,t(PnPn¯)≤n+2.
It can be easily proved that γt(PnPn¯)=n, where n=2,3. Next proposition calculates γt(PnPn¯) when n≥4.Proposition 3.12.
Letn≥4. Then
(3.36)γt(PnPn¯)={2⌈n-24⌉+1ifn≡3(mod⁡4),2⌈n-24⌉+2otherwise.Proof.
LetD be a γt-set of the induced path Pn[V(Pn)-{1,n}] of Pn. Since D∪{1¯,n¯} is a TDS of PnPn¯, we have
(3.37)γt(PnPn¯)≤|D∪{1¯,n¯}|={2⌈n-24⌉+1ifn≡3(mod⁡4),2⌈n-24⌉+2otherwise.
Let n≡2(mod4). Then chains (3.34), (3.35), (3.37) imply γt(PnPn¯)=2⌈(n-2)/4⌉+2. Since 2⌈n/4⌉=2⌈(n-2)/4⌉+2. Now let n≢2(mod4), and let S be a TDS of PnPn¯.  Obviously S∩V(Pn¯)≠∅. In all cases, (i) |S∩V(Pn¯)|=1 and S∩{1¯,n¯}≠∅, (ii) |S∩V(Pn¯)|=1 and S∩{1¯,n¯}=∅, and (iii) |S∩V(Pn¯)|≥2, then similar to the proof of Proposition 3.11, it can be verified that
(3.38)|S|≥{2⌈n-24⌉+1ifn≡3(mod⁡4),2⌈n-24⌉+2otherwise.
Hence chain (3.37) completes the proof of our proposition.Propositions3.11 and 3.12 imply the next result in [1].Corollary 3.13 (see [1]).
IfG∈{Pn,Cn} with order n≥5, then
(3.39)γt(GG¯)={γt(G)ifn≡2(mod⁡4),γt(G)+2ifn≡0(mod⁡4),γt(G)+1otherwise.


## 4. Problems

If we look carefully at the propositions of Section3, we obtain the following result.Proposition 4.1.
(i) LetG be a cycle or a path of order n≥4. Then max{γt(G),γt(G¯)}=γt(GG¯) if and only if n≡2(mod4).
(ii) LetG be a cycle of order n≥5 or a path of order n≥4. Then γt(GG¯)=γt(G)+γt(G¯) if and only if n≡0(mod4).
(iii) LetCn be a cycle of order n≥5. Then
(4.1)max⁡{γ×2,t(Cn),γ×2,t(Cn¯)}<γ×2,t(CnCn¯)<γ×2,t(Cn)+γ×2,t(Cn¯).
(iv) LetCn be a cycle of order n≥5. Then
(4.2)γt(Cn)+γt(Cn¯)<γ×2,t(CnCn¯)=n+min⁡{γt(Cn),γt(Cn¯)}.Therefore it is natural that we state the following problem.Problem 1.
Characterize graphsG with(1)
γ×k,t(GG¯)=γ×k,t(G)+γ×k,t(G¯),(2)
γ×k,t(G¯)=max{γ×k,t(G),γ×k,t(G¯)}.



---

*Source: 681274-2012-01-18.xml*