An Effect of Total Domination upon Edge-Vertex Removal of Graphs

An Effect of Total Domination upon Edge-Vertex Removal of Graphs

Dr.(Mrs). B. Tamilselvi

Head of the Department of Mathematics P.S.G.R.Krishnammal College for Women, Coimbatore, India,

Mrs. S. K. Sathya

M.Phil Degree P.S.G.R.Krishnammal College for Women,

Coimbatore, India.

Abstract – Graphs which are critical with respect to the total domination have been studied by several authors. This paper is concerned about what happens to total domination number when an edge or vertex is removed from the graph. Several references are used to include all the results of this paper.

Keywords: Total Dominating set, Minimum Total dominating set, Total domination number, Subgraph, Pendant Edge, Star, Double Star.

INTRODUCTION

Total Domination is undefined for graphs with isolated vertices. The graph is a total domination edge critical or – critical for short, if the removal of any edge in the graph changes the total domination number, that is

( ) () for every edge (). Note that removing an edge from a graph cannot decrease the total domination number. Hence if is – critical, then

( ) > () for every edge (). Thus, every edge in a – critical graph is a critical edge.

Let be a graph. A vertex of is said to be a

pendant vertex (or leaf) if and only if it has degree 1. An edge of a graph is said to be pendant if one of its vertices is a pendant vertex.

1,

1,

A tree if is a nontrivial star, or a double star, or if can be obtained from a subdivided star , where 2, by adding zero or more pendant edges to the

1,

1,

non-leaf vertices of . A tree containing exactly one

vertex that is not a pendant vertex is called a star. The double star (, ) is a tree of diameter three such that there are pendant edges on one end of path 2 and pendant edges on the other end.

1. EDGE CRITICAL GRAPHS

   1,

   1,

   This Section computes a characterization of -critical

   galaxy of nontrivial stars.

   Theorem 1.2 A connected graph is -critical if and only if .

   Proof Assume that = (, ) is -critical. Let be any ()-set. By Lemma 1.1, [] is a galaxy of nontrivial stars. If is a leaf in [] and is adjacent to a vertex of degree at least two in [], then by Proposition 1.1,|(, )| > 1. Thus, has an external private neighbor and is therefore adjacent to at least one vertex in

   \. For every edge of , if is a total dominating set in

   ,then ( ) || = (),contradicting the fact that is -critical. Hence for every edge of , the set is not a total dominating set in . This implies that

   \ is an independent set and that each vertex in \ is adjacent to exactly one vertex of and is therefore a leaf in . Thus since is connected, the subgraph [] is connected. Hence, [] is a star. If [] = 2, then is either a star or a double star, and so . Hence assume that [] is a star 1, where 2. As observed earlier, each leaf in the star [] is adjacent to at least one vertex in \. Let denote a set of vertices in \ that dominate the set of leaves in []. Then, [ ] =

   1,

   1,

   and can be obtained from this subdivided star by

   adding zero or more pendant edges to each vertex of . Thus, .

   Now, assume that . Let = (, )and let

   . If is incident with a leaf in , then ( ) =

   , and so is a critical edge. Hence, assume that is not incident with a leaf in . In particular, is not a star. If

   is a double star, then joins the two central vertices of .

   Thus, ( ) = 4 while () = 2, and so is a critical

   graph.

   edge. Hence assume that is not a double star. Thus, is obtained from a star = , for some 2, by adding

   Proposition 1.1 If is a minimal total dominating set of connected graph , then for each vertex ,

   |(, )| 1 or [\{}] contains an isolated vertex.

   Lemma 1.1 If is a -critical graph, then for every ()- set , [] is a galaxy of nontrivial stars.

   Proof Let be any () -set in the -critical graph , and let =[]. Let be an arbitrary edge in . If both ends of have degree at least 2 in , then is a total dominating set in , and so ( ) || = (), contradicting the fact that is -critical. Hence at least one end of the edge is a leaf in , implying that is a

   at least one pendant edge to each leaf of and adding zero or more pendant edges to the center of the star . Every edge in the set \() is incident with a leaf in . Hence, by earlier assumptions, (). But then ( ) =

   + 2 while () = + 1 (irrespective of whether is a support vertex of ). Hence, once again, the edge is a

   critical edge. Therefore, is -critical.

2. VERTEX CRITICAL GRAPHS

   Proof (i) Let be any graph and () such that

   . Let + and be a minimum total dominating set in

   When a vertex is removed from a graph, the total

   domination number may increase, decrease or remains unchanged. Here three sets namely +, and 0 in a

   the graph containing . Suppose [, ] = {}. To show that . Suppose . Therefore, is adjacent

   to only in . But + imply . Therefore, the

   graph are defined. All graphs are simple and a total dominating set contains at least two vertices. Also graphs considered have no isolated vertices.

   If is a graph then () will denote the vertex set of . If is a vertex of , then will denote the subgraph obtained by removing the vertex from the graph. Let be a graph. A subset of () is said to be a total dominating set in the graph if any vertex of the graph is adjacent to at least one vertex of the set . A total dominating set in the graph is said to be a minimal total dominating set in the graph if for any vertex of ,

   is not a total dominating set in the graph . Definition: Let be any graph. Then,

   = { () / has an isolated vertex}.

   + = { () / ( ) > ()}.

   = { ()/ ( ) < ()}.

   0 = { () /( ) = ()}.

   Theorem 2.1 Let be any graph and () such that

   graph does not contain any isolated vertex. Therefore, find some vertex such that is adjacent to (because if ,then [, ]). Let 1 = {} {}.

   Case 1. If = , then is adjacent to a vertex 1.

   Case 2. If ( ), then is adjacent to some vertex different from (because is a total dominating set in the graph and therefore if is adjacent to only , then [, ] contains different from , a contradiction to the fact that

   [, ] = {}). That is if ( ), then is adjacent to some vertex 1.

   Case 3. If = , then is adjacent to a vertex 1. Thus, from all cases can say that 1 is a total dominating set in the graph not containing with |1| = (). That is, 1 is a -set in the graph not containing , a

   +

   contradiction to the fact that +. Therefore, .

   . Then

   are satisfied:

   if and only if the following conditions

   (ii) Suppose + and is a minimum total

   (a) Every -set of te graph contains .

   (b) If is a subset of () [] such that || = (), then is not a total dominating set in .

   Proof The proof is standard and hence it is omitted.

   Theorem 2.2 Let be any graph and let () with

   . If for any (), the subgraph induced by ()

   is complete, then .

   Proof Let be any graph and () such that .

   dominating set in containing . Therefore, Let be a

   graph and be a subset of (). A total dominating set S in the graph is a minimal total dominating set in if and only if for every vertex , [, ] . Suppose,

   [, ] = {}. Therefore, (by Theorem 2.3(i)). Also . Therefore, the graph does not contain any isolated vertex. Therefore, there is a vertex in

   () such that is adjacent to .(because if is adjacent to only in , then contains an isolated vertex

   and therefore , a contradiction to the fact that ).

   Let the subgraph induced by () be complete for every

   (). To prove . Suppose . Therefore, there is a minimum total

   Also (because if , then is adjacent to two distinct vertices , of and therefore [, ], a

   dominating set

   in the graph not containing and a

   contradiction to the fact that [, ] = {}). But is a

   vertex in such that [, ] = {}. Therefore, is adjacent to only one vertex in . Therefore, (). Also, and is a total dominating set in the graph . Then, is adjacent to some vertex in . Therefore both and are in (). But, the subgraph induced by () is complete. Therefore, is adjacent to a vertex . Therefore,

   is adjacent to two distinct vertices , of . Therefore,

   [, ], a contradiction to the fact that [, ] =

   {}. Therefore, the assumption is wrong. Therefore,

   .

   total dominating set in . Therefore, is adjacent to some vertex different from (because if is adjacent to only in , then [, ] contains one element

   different from , a contradiction to the fact that

   [, ] = {}). Let 1= {} {}.

   Case 1. If = , then is adjacent to a vertex 1. Case 2. If ( ), then is adjacent to some vertex different from (because is a total

   dominating set in the graph and if is adjacent to only

   + , then [, ] contains different from , a

   Theorem 2.3 Suppose and is a minimum total

   contradiction to the fact that [, ] = {}). That is, if

   dominating set in the graph containing with .

   Then the following statements are true: (i) If [, ] = {}, then .

   ( ), then is adjacent to some vertex 1.

   Case 3. If = , then is adjacent to some vertex in

   1. [, ] contains at least two vertices different from

      .

   2. If [, ] contains more than one vertex an 1 , 2, are such adjacent vertices, then at least one .

   (because is a total dominating set in the graph ). Therefore = , then is adjacent to some vertex in 1. Thus, from all cases can say that 1 is a total dominating set in the given graph not containing with |1| =

   ().Therefore, 1 is a -set in the graph not

   containing , a contradiction to the fact that +.

   Case 3. Let 1, 2 . If 1 + and 2 +, then

   Therefore, [, ] contains at least two vertices.

   1, 2 0. Thus, a vertex + gives rise to two distinct

   Therefore, [, ] contains at least two vertices

   vertices of 0. If 1 + and 2 +, then from case 2, say

   different from . that a vertex + gives rise to two distinct vertices of 0. If

   1, 2 +, then as per above case, there exists two

   (iii) Let 1, 2 [, ] and 1, 2 are two adjacent

   distinct v

   s ,

   such that [ , ], for = 1, 2

   vertices. Suppose ,

   . Therefore,

   is adjacent

   ertice 1 2

   to

   and , both

   1 2

   e . Therefore,

   1

   [, ], a

   with both 1, 2 (because if , then is adjacent

   2 ar in 1 [

   to and , both are in and therefore [, ], =

   contradiction to the fact that 1 , ]. Therefore, the

   , 2). Hence, 1, 2 + (by theorem 2.1). But is

   assumption is wrong. Therefore, at least one for =

   adjacent to

   and

   + for = 1, 2. Therefore,

   1,2.

   Theorem 2.4 Let be any graph and = . If + and

   , = 1, 2 (by theorem

   2.4). Therefore,

   +

   1, 2 0.Therefore, a vertex

   gives rise to two

   , then and are non-adjacent vertices. 0 +

   Proof Let be any graph. Let V+ and . Suppose

   distinct vertices of . Thus, proved that every vertex

   gives rise to at least two distinct vertices of 0. Suppose 1 and

   T

   2 are two distinct vertices of + such that 1, 2 0

   and are adjacent. Since , there is a minimum total

   corresponds to

   with respect to a

   2

   2

   -set in in the graph

   dominating set in the graph not containing and a vertex

   S different from such that [, ] = {} (because if

   = and + such that , then by theorem 2.3(ii),

   1 and 3, 4 0 corresponds to a vertex with respect to the same -set .

   [, ] contains at least two vertices different from , a contradiction to the fact that [, ] = {}). But +.Therefore S.Therefore, is adjacent to two vertices and , both are in . Therefore [, ], a contradiction to the fact that [, ] = {}. Therefore, the assumption is wrong. Therefore, and are non-

   1 2

   1 2 3 4

   Fig 1

   adjacent.

   0

   Here the possibility for is either or . Suppose 2 =

   Theorem 2.5 Let be any graph and = . Then, | | 2|+|.

   3. Then, 2 is adjacent to two distinct vertices of . Therefore, 2 [, ] for any . Therefore, 2

   +

   [, ], for = 1, 2, 1, 2, a contradiction. Thus,

   Proof Let be any graph and = . Let and be

   proved that two distinct vertices of + gives rise to two

   a -set in the graph containing . Therefore by theorem

   distinct two elements sets of 0. Therefore, | 0| 2| +|.

   2.3(ii), [, ] contains at least two vertices ,

   1 2

   different from . Since 1 is adjacent to , 1 (by

   Theorem 2.6 Let be any graph and = . If

   theorem 2.4. Similarly say that 2

   .

   ( ) () for every vertex (), then

   Case 1. Suppose 1 , 2 .Therefore 1, 2 +(by theorem 2.1). Therefore 1, 2 0. Thus, a vertex

   ( ) < () for every ().

   + 0 Proof To prove that . That is, = (). Since

   VT gives rise to at least two vertices of .

   0

   ( ) () for every (), for every

   (). Therefore, 0 = . Therefore, | 0| = 0. But

   Case 2. Suppose 1 or 2 belongs to . Without loss of

   | 0| 2| +| (by th

   em 2.4). Therefor | +| = 0.

   generality, suppose 1 and 2 . From the above

   eor

   e,

   0 + 0

   Therefore, + = . Also given that = . But,

   case, 2 . If 1 , then 1 . Thus, a vertex of

   0

   + give rise to at least two vertices of 0. If 1 +, then by

   = (). Therefore,() = . Therefore,

   theorem 2.3(ii), [1, ] contains at least two vertices different from 1 in which one vertex(say) 1 is different from and 1 (because if 1 , then 1 is adjacent to two vertices and 1, both are in S and therefore 1

   [, ]. Therefore 1 +(by theorem 2.1) and 1 is adjacent 1. It follows that 1 (by theorem 2.4). Therefore, 1 0. Also,2 [1, ] (because if

   2 [1, ], then 1 is adjacent to and 2(both are in ) and therefore 1 [, ], a contradiction to the fact 1 [, ]). Therefore, 1 2 and 1, 2 0. Thus, a vertex + gives rise to two distinct vertices of

   0.

   ( ) < () for every ().

3. CONCLUSION

Finally this paper concludes that if the total domination number changes whenever every edge is removed, then the total domination number increases. Accordingly, the total domination number decreases after the removal of any vertex.

ACKNOWLEDGMENT

The authors thank the referees for a careful reading of the manuscript. The authors also gratefully acknowledge the support of the P.S.G.R.Krishnammal College for Women for the valuable support.

REFERENCES

[1]. J.R.Carrington, F.Harray, and T.W.Haynes. Changing and unchanging the domination number of a graph. J.Combin. Comput., the 9:57-63,1991.

[2]. E.J.Cockayne, R.M.Dawes, and S.T.Hedetniemi. Total Domination in graphs. Networks, 10:211-219,1980.

[3]. Teresa W.Haynes, Stephen T.Hedetniemi, Peter J.Slater. Domination in Graphs(Advanced Topics) Marcel Dekker Publication, New York, 1988.

[4]. Teresa W.Haynes, Stephen T.Hedetniemi, Peter J.Slater. Fundamental of Domination in Graphs, Marcel Dekker Publication, New York, 1988.

[5]. W.J.Desormeaux, T.W.Haynes, and M.A.Henning, Total domination critical and stable graphs upon edge removal. Discerete Appl.Math. 158 (2010) 1587-1592.

[6]. H.B.Walikar and B.D.Acharya, Domination Critical Graphs. Nat.

Acad. Sci. Lett. 2 (1970) 70-72.

[7]. L.C.Van der Merwe, Total Domination Edge Critical Graphs. Ph.D. Thesis, University of South Africa, 1999.