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

DOI : 10.17577/IJERTV5IS080197

Text Only Version

#### 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,

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 =

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

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.