The Inverse Split and Non-split Domination in Graphs

The Inverse Split and Non-split Domination in Graphs

(1)Mr. N.Karthikeyan

(1) Head, Department of Mathematics, Kongunadu College of Engg & Tech, Trichy

(2) Ms. S.Hema

(2) Student,

Kongunadu College of Education, Trichy.

Abstract – In this paper, we define the notions of inverse split and non splitdomination in graphs. We get many bounds on inverse split andnon split domination numbers. Nordhaus-Gaddum type results are also obtained for these new parameters.

Keywords: Independent set, dominating set, split dominatingset, non-split dominating set, inverse split dominating set,inverse non-split dominating set, inverse split and non-splitdomination numbers.

Definition: 4.1

A non- empty set D V of a graph G is a dominating set of G if every vertex in V-D is adjacent to some vertex in D. The domination number (G) is the minimum cardinality taken over all the minimal dominating sets of G. Let D be the minimum dominating set of G. If V-D contains a dominating set D then D is called the Inverse dominating set of G w.r.to

D. The Inverse dominating number (G) is the minimum cardinality taken over all the minimal inverse dominating sets of G. A dominating set D of G is a connected dominating set if the induced subgraph <D> is connected. The connected domination number c(G) is the minimum cardinality of a connected dominating set. Unless stated, the graph G has n vertices and m edges. A dominating set D V of a graph G is a split (non-split) dominating set if the induced subgraph <V-D> is disconnected (connected). The split (non-split) domination number s(G) (ns(G)) is the minimum cardinality of a split (non-split) dominating set.

Example 4.2

Consider the following graph in figure 1.

6 2

5 1

4 3

Graph G: Figure 1

Here D 3, 4

D' 1, 5

V D' 2,3, 4, 6

(G) 2 & '(G) 2

'ns (G) 2 When D 1, 5 D' 2, 4

V D' 1,3,5, 6

(G) 2 & '(G) 2

's (G) 2

Theorem 4.3

For any graph Proof

'(G) 's (G) &

'(G) 'ns (G)

Since every inverse split dominating set of G is an inverse dominating set of G, we have

'(G) 's (G)

Similarly every inverse n o n – split dominating set of G is an inverse dominating set of G, we have

'(G) 'ns (G)

Theorem 4.4

Proof

For any graph G,

(G) = min { s (G) , ns (G) }

Since every inverse split dominating set and every inverse non-split dominating set of G are the inverse dominating set

of G.

We have

'(G) 's (G) and

'(G) 'ns (G)

And hence (G) = min { s (G) , ns (G) }

Theorem 4.5

Let T be a tree such that any two adjacent cut vertices u and v with atleast one of u and v is adjacent to an end vertex

then Proof

'(T ) 's (T )

Let D be a set of T, and then we consider the following two cases:

Case (i)

Suppose atleast one of the theorem is true.

Case (ii)

u, v D', then <V-D> is disconnected with atleast one vertex. Hence D is a set of T. thus

Suppose u, v V D', since there exists an end vertex adjacent to either u or v say u, it implies that

D'

Thus it follows that

D'' D'u

set of T.

Hence by case (i), the theorem is true

Theorem 4.6

For any tree T, 'ns (T ) n p where p is prime number of vertices adjacent to end vertices.

Theorem 4.7

For any graph G, 'ns (G) n (G) , where (G)

is the minimum degree among the vertices of G.

Note 4.8

For any tree T, (T ) 1

Hence 'ns (T ) n 1

Remarks 4.9

We obtained the relationship between 'ns (G) and 'ns (H ) where H is any connected spanning subgraph of G.

similar result for 's (G) and 's (H )

If H is any connected spanning subgraph of G then '(G) '(H )

Theorem 4.10

Let G be a graph which is not a cycle with atleast 5 vertices. Let H be a connected spanning subgraph of G then

(i) 'ns (G) 'ns (H )

(ii) 's (G) 's (H )

Proof

Since G is connected then any spanning tree T of G is minimally connected subgraph of G such that

's (G) 's (T ) 's (H )

In a similar way 'ns (G) 'ns (T ) 'ns (H )

Hence the proof.

Theorem 4.11

If T is a tree which is not a star then 'ns (T ) n 2 n 3.

Proof

Since T is not a star, there exists two adjacent cut vertices u and v with degree u and degree v 2.this implies that V-

{u,v}is an inverse non-split dominating set of T. Thus the theorem is true.

CONCLUSION

Graph theory serves as a model for any binary relation. In domination, both dominating sets and their inverses have important roles to play. Whenever, D is a dominating set, V-D is also a dominating set. In an information retrieval system, we always have a set of primary nodes to pass on the information. In case, the system fails, we have another set of secondary nodes, to do the job in the complement. When the complement set is connected, then there will be flow of information among the members of the complement. Thus, the dominating sets and the elements in the inverse dominating sets can stand together to facilitate the communication process. They play very vital role in coding theory, computer science, operations research, switching circuits, electrical networks etc.

Thus in this paper, we defined the notions of inverse split and non split domination in graphs. We got many bounds on inverse split and non split domination numbers. Nordhaus- Gaddum type results are also obtained for these new parameters. Edge analog of these two parameters are also discussed in a detailed manner.

REFERENCES

1. Ameenal Bibi, K. and Selvakumar, R (2008). The Inverse split and non- split domination numbers in graphs. Proc. of the International Conference on Mathematics and Computer Science, ICMCS 2008, Dept. of Mathematics, Loyola College, Chennai 600034. July 25-26.

2. Ameenal Bibi, K. and Selvakumar, R (2009). The Inverse strong non-split r-domination number of a graph. Proc. of the National Conference on Industrial Applications of Mathematics, NCMA 2009, PG and Research Dept. of Mathematics, Sacred Heart College (Autonomous) Tirupattur, Vellore Dist., March 12-13.

3. Ameenal Bibi, K. and Selvakumar, R (2010). The inverse strong non-split r-domination number of a graph International Journal of Engineering, science and Technology, Vol.2, No. 1, pp. 127-133.; www.ijest_ng.com, ISSN No. for IJEST:

   For printed version : 2141-2820 For online version : 2141-2839.

4. Harary F., Graph Theory, Addition Wesley, Reading Mass, 1969.

5. Haynes T.W., Hedetniemi S.T and Slater P.J., Fundamentals of Domination in Graphs, Marcel Dekker New York (1998)

6. Kulli V.R.and Jankiram B., The Split Domination number of a Graph. Graph Theory Notes of New York academy of science (1997) XXXII,

7. Kulli V.R. and Jankiram B., The Nonsplit Domination number of a graph, Indian J. pure appl. Math. 31(5): 545 550 May 2000.

8. Narsingh Deo, Graph Theory with Applications to Engineering and Computer Science , June 2003.

9. Ore O., Theory of graphs, Amer.Math.Soc.Colloq. Pub., 38 Providence (1962)