Total Domination Subdivision Number in Strong Product Graph

P. Jeyanthi, G. Hemalatha, B. Davvaz

  Open Access OPEN ACCESS  Peer Reviewed PEER-REVIEWED

Total Domination Subdivision Number in Strong Product Graph

P. Jeyanthi1,, G. Hemalatha2, B. Davvaz3

1Department of Mathematics, Govindammal Aditanar College for Women, Tiruchendur, Tamil Nadu, India

2Department of mathematics, Shri Andal Alagar College of Engineering, Mamandur, Kancheepuram, Tamil Nadu, India

3Department of Mathematics, Yazd University, Yazd, Iran

Abstract

A set D of vertices in a graph G(V,E) is called a total dominating set if every vertex v∈V is adjacent to an element of D. The domination subdivision number of a graph G is the minimum number of edges that must be subdivided in order to increase the domination number of a graph. In this paper, we determine the total domination number for strong product graph and establish bounds on the total domination subdivision number for strong product graph.

At a glance: Figures

Cite this article:

  • Jeyanthi, P., G. Hemalatha, and B. Davvaz. "Total Domination Subdivision Number in Strong Product Graph." American Journal of Applied Mathematics and Statistics 2.4 (2014): 216-219.
  • Jeyanthi, P. , Hemalatha, G. , & Davvaz, B. (2014). Total Domination Subdivision Number in Strong Product Graph. American Journal of Applied Mathematics and Statistics, 2(4), 216-219.
  • Jeyanthi, P., G. Hemalatha, and B. Davvaz. "Total Domination Subdivision Number in Strong Product Graph." American Journal of Applied Mathematics and Statistics 2, no. 4 (2014): 216-219.

Import into BibTeX Import into EndNote Import into RefMan Import into RefWorks

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´ıguez-Vel´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.

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:

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:

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), 211-219.
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), 115-128.
In article      
 
[4]  W. Haynes and Michael A. Henning, Total domination subdivision numbers of graphs, Discussiones Mathematicae Graph Theory 24(2004), 457-467.
In article      CrossRef
 
[5]  Teresa W. Haynes, Michael A. Henning and Lora Hopkins, Total domination subdivision numbers of trees, Discrete Mathematics 286(2004), 195-202.
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), 2419-2432.
In article      
 
[8]  N. Soltankhah, Results on total domination and total restrained domination in grid graphs, International Mathematical Forum, 5(7) (2010), 319-332.
In article      
 
[9]  S. Gravier, Total domination number of grid graphs, Discrete Applied Mathematics, 121 (2002) 119-128.
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´ıguez-Vel´azquez, Roman domination in Cartesian product graphs and Strong product graph, Discrete Math., 7(2013), 262-274.
In article      
 
  • CiteULikeCiteULike
  • MendeleyMendeley
  • StumbleUponStumbleUpon
  • Add to DeliciousDelicious
  • FacebookFacebook
  • TwitterTwitter
  • LinkedInLinkedIn