 Open Access
 Total Downloads : 106
 Authors : Dr. (Mrs). B. Tamilselvi, Mrs. S. K. Sathya
 Paper ID : IJERTV5IS080197
 Volume & Issue : Volume 05, Issue 08 (August 2016)
 DOI : http://dx.doi.org/10.17577/IJERTV5IS080197
 Published (First Online): 19082016
 ISSN (Online) : 22780181
 Publisher Name : IJERT
 License: This work is licensed under a Creative Commons Attribution 4.0 International License
An Effect of Total Domination upon EdgeVertex 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,
nonleaf 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.

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.

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

[, ] contains at least two vertices different from
.

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
[, ], awith 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 nonadjacent 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 ().

[, ] contains at least two vertices different from

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:5763,1991. [2]. E.J.Cockayne, R.M.Dawes, and S.T.Hedetniemi. Total Domination in graphs. Networks, 10:211219,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) 15871592. [6]. H.B.Walikar and B.D.Acharya, Domination Critical Graphs. Nat.Acad. Sci. Lett. 2 (1970) 7072.
[7]. L.C.Van der Merwe, Total Domination Edge Critical Graphs. Ph.D. Thesis, University of South Africa, 1999.