Keywords: total dominating set, strong product graph, total domination number
American Journal of Applied Mathematics and Statistics, 2014 2 (4),
pp 216219.
DOI: 10.12691/ajams247
Received June 03, 2014; Revised July 25, 2014; Accepted July 28, 2014
Copyright © 2013 Science and Education Publishing. All Rights Reserved.
1. Introduction
Let be a simple graph on the vertex set V. In a graph G, a set is a dominating set of G if every vertex in is adjacent to some vertex in D. The domination number of a graph G is the minimum size of a dominating set of vertices in G, denoted by . A thorough study of fundamental domination appears in ^{[2]}. The concept of total domination in graphs was introduced by Cokayne, Dawes and Hedetemini ^{[1]}. A set of vertices in a graph is called a total dominating set if every vertex is adjacent to an element of S. The total domination number of some cartesian products of two paths and , are investigated in ^{[8, 9]}. The values of for n = 2, 3, 4 are determined in ^{[8]}, and for n = 5, 6 are determined in ^{[9]}.
Let G and H be the two graphs with the set of vertices and respectively. The strong product of G and H is the graph formed by the vertices and two vertices and are adjacent in if and only if or Domination number is rather difficult to construct graphs with large value of and the first conjecture on this subject was that for every G ^{[10]}. The concept of total domination subdivision number was due to Haynes et al ^{[3]}. Haynes et.al ^{[4]} studied the total domination subdivision number of graphs, for instance, they showed that holds for a graph having three or more pair wise adjacent simplicial vertices. In ^{[5]} the authors proved the total domination subdivision number of trees. Constant upper bounds on the total domination number for several families of graphs were determined in ^{[3]}. Nasrin Soltankhah showed that for any ^{[7]}. The behaviour of several graph parameters in product graphs has become an interesting topic of research ^{[6]}. G. Yero and J. A. Rodr´ıguezVel´azquez ^{[11]} proved that for any In this paper is to establish a bound of this type on
2. Main Result
In this section, we first determine the value of the total domination number of for Since we have:
Proposition 2.1. For any we have
Lemma 2.2. We have
Proof: To obtain totally dominate the vertices and we need two vertices and Therefore, . Last column of is totally dominated by Hence, Let us consider as block B. The last three columns of is block B. The first column of can be totally dominated by B. Hence, In , to totally dominate a vertex we need one vertex among Hence, The first three columns of is block B and also the last column of is totally dominated by the fourth column. This completes the proof.
Proposition 2.3. For any , we have
Proof:
Figure 1.
Figure 1.
Let S be a total dominating set of Since Suppose that and are four consecutive columns of To totally dominate the vertices and we need one vertex among and one more vertex among Now, to describe the total dominating set S, we consider block and If then can be partitioned with number of blocks B. If then can be partitioned with number of blocks B, plus a block and . If then can be partitioned with number of blocks B, plus a block and . If then can be partitioned with number of blocks B, plus a block and This completes the proof.
Proposition 2.4. For the total domination number of and are same.
Proof: Last two rows of is considered as blocks and the first row of is totally dominated by B, which completes the proof.
Observation 2.5. For , we have
Proposition 2.6. For any we have
Proof:
Figure 2.
Suppose that S is a total dominating set of . Let us consider as block. Since the total domination number of is 2. We have . Let and be three consecutive columns of To totally dominate the vertices and we need one vertex among and one more vertex among
Now, to describe our total dominating set S, we consider block . If then can be partitioned with number of blocks B. If then can be partitioned with number of blocks B, plus a block and If then can be partitioned with number of blocks B, plus a block and This completes the proof.
Theorem 2.7. We have
Proof:
Figure 3.
Let S be a total dominating set of Since each column of is isomorphic to By Proposition 2.1 and Observation 2.5, we have
Let us consider as block. Now to describe our total dominating set S, we consider block If then can be partitioned with number of blocks B. By Proposition 2.1 and Observation 2.5, we obtain If then can be partitioned with number of blocks B. By Proposition 2.1 and Observation 2.5, we obtain This completes the proof.
3. Subdivision Number for the Strong Product Graph
Proposition 2.8. For we have
Proof: Let be a total dominating set of and Let be obtain from by subdividing an edge and adding new vertex called Now, there is no change in total domination number, i.e,
Let be obtain from by subdividing the edges and adding new vertices respectively called and So, we need three vertices for totally domination. Therefore,
Thus, By Lemma.2.2, we obtain that the total domination number of is greater than the total domination number of This completes the proof.
Proposition 2.9. For , we have
Proof: To describe our total dominating set S, we consider block and Since Thus, we have
Proposition 2.10. For we have
Proof: Let be a total dominating set of and Let be obtain from by subdividing an edge and adding new vertex called To totally dominate we need one vertex among Therefore, Thus,
By Lemma 2.2, we obtain that the total domination number of is greater than the total domination number of This completes the proof.
Proposition 2.11. For we have
Proof: Let be a total dominating set of and Let be obtain from by subdividing an edge and adding new vertex called To totally dominate we need one vertex among Therefore, Thus, By Lemma 2.2, we obtain that the total domination number of is greater than the total domination number of This completes the proof.
Theorem 2.8. For we have
Proof: To describe our total dominating set S, we consider block and Since and by Proposition 2.3, we have
Theorem 2.9. For subdivision number of and are same.
Proof: Last two rows of is considered as blocks and the first row of is totally dominated by B, which completes the proof.
Theorem 2.10. For we have
Proof: To describe our total dominating set S, we consider block and By Theorem 2.9, we have Thus,
Theorem 2.11. For we have
Proof: To describe our total dominating set S, we consider block By Theorem 2.10, we have Thus,
References
[1]  E.J. Cockayne, R.M. Dawes and S.T. Hedetniemi, Total dominations in graphs, Networks, 10 (1980), 211219. 
 In article  CrossRef 

[2]  T.W. Haynes, S. T. Hedetniemi and P. J. Slater, Fundamentals of Domination in Graphs, Marcel Dekker, New York, 1997. 
 In article  

[3]  T.W. Haynes, S.T. Hedetniemi and L.C. van der Merwe, Total domination subdivision numbers, J. Combin. Math. Combin. Comput., 44 (2003), 115128. 
 In article  

[4]  W. Haynes and Michael A. Henning, Total domination subdivision numbers of graphs, Discussiones Mathematicae Graph Theory 24(2004), 457467. 
 In article  CrossRef 

[5]  Teresa W. Haynes, Michael A. Henning and Lora Hopkins, Total domination subdivision numbers of trees, Discrete Mathematics 286(2004), 195202. 
 In article  CrossRef 

[6]  W. Imrich, S. Klavˇzar, D. F. Rall, Topics in Graph Theory. A. K. Peters Ltd., Wellesley, MA, 2008. 
 In article  

[7]  N.Soltankhah, On total domination subdivision number of grid graphs, Int.J.Contemp.Math.Sciences, 5(49) (2010), 24192432. 
 In article  

[8]  N. Soltankhah, Results on total domination and total restrained domination in grid graphs, International Mathematical Forum, 5(7) (2010), 319332. 
 In article  

[9]  S. Gravier, Total domination number of grid graphs, Discrete Applied Mathematics, 121 (2002) 119128. 
 In article  CrossRef 

[10]  S. Velammal, “Studies in Graph Theory”, Ph.D. Thesis (Manonmaniam Sundaranar University, Tirunelveli, 1997. 
 In article  

[11]  G. Yero, J. A. Rodr´ıguezVel´azquez, Roman domination in Cartesian product graphs and Strong product graph, Discrete Math., 7(2013), 262274. 
 In article  
