To Find A 2-Tuple Dominating Set of an Induced Subgraph of a Non-Split Dominating Set of an Interval Graph Using an Algorithm

To Find A 2-Tuple Dominating Set of an Induced Subgraph of a Non-Split Dominating Set of an Interval Graph Using an Algorithm

TO FIND A 2-TUPLE DOMINATING SET OF AN INDUCED SUBGRAPH OF A NON- SPLIT DOMINATING SET OF AN INTERVAL GRAPH USING AN ALGORITHM

Dr.A.Sudhakaraiah*, E. Gnana Deepika1, V. Rama Latha2

Department of Mathematics, S. V. University, Tirupati-517502, Andhra Pradesh, India.

ABSTRACT:

In Graph Theory, a connected component of an undirected graph is a sub graph in which any two vertices are connected to each other by paths. For a graph G , if the subgraph G itself is a connected component then the graph G is called connected, else the graph G is called disconnected and each connected component sub graphs is called its components. A dominating

set D a of graph G(V , E) is a non-split dominating set, if the induced subgraph V D is

connected. The non-split dominating number

ns (G)

of G is the minimum cardinality of a non-

split dominating set. The 2-tuple domination problem is to find a minimum size vertex subset such that every vertex in the graph is dominated by at least 2 vertices in the set. In this paper we discussed an algorithm to find a 2-tuple dominating set of an induced subgraph of a non-split dominating set of an interval graph.

Key Words: Interval family, Interval graph, connected graph, Dominating Set, Non-split dominating set, 2-tuple domination, design of an algorithm.

1. INTRODUCTION

   An undirected graph G

   (V , E) is an interval graph(IG), if the vertex set V can be put

   into one-to-one correspondence with a set of intervals I on the real line R , such that two vertices are adjacent in G , if and only if their corresponding intervals have non-empty intersection. The set I is called an interval representation of G and G is referred to as the intersection graph I .

   Let

   I I1, I2 , I3 , I4 ,………In

   be any interval family where each Ii

   is an interval on the real line

   and Ii

   ai , bi

   for i

   1, 2,3, 4,……….n . Here ai

   is called the left end point labeling and

   bi is the

   right end point labeling of

   Ii .Without loss of generality we assume that all end points of the

   intervals in I are distinct numbers between 1 and 2n . Two intervals i and j are said to be intersect each other if they have non empty intersection. Also we say that the intervals contains both its end points and that no two intervals share a common end point. The intervals and

   vertices of an interval graph are one and the same thing. The graph G is connected, and the list of sorted end point is given and the intervals in I are indexed by increasing right end points, that is

   b1 b2

   b3 ……..

   bn .

   Let G(V , E) be a graph. A set S is a dominating set of G if every vertex in V D is

   adjacent to some vertex in D . The domination number

   (G)

   of G is the minimum cardinality

   of a dominating set[7]. A dominating set D of G is connected dominating set, if the induced sub

   Note:- * corresponding Author

   graph V D is connected. The connected domination number

   c (G) of G is the minimum

   cardinality of a connected dominating set. A dominating set D of a graph G(V , E) is a non-split

   dominating set if the induced sub graph V D is connected. The non-split domination

   number

   ns (G)

   of G is the minimum cardinality of a non-split dominating set[3].

   In a graph G, a vertex is said to dominate itself and all of its neighbors. A dominating set of G V , E is a subset D of V such that every vertex in V is dominated by at least one vertex in

   D . The domination number G is the minimum size of a dominating set of G [7]. For a fixed

   positive integer m an m -tuple dominating set of G V , E is a subset D of V such that every

   vertex in V is dominated by at least m vertices of D . As introduced by Harary and Haynes[6],

   a m -tuple dominating set D is a set D V for which

   N[v] D

   m for every v V , where

   N[v]

   {v}

   {u V : (u,v)

   E} is the closed neighborhood of the vertex v [1,2]. A double

   dominating set D is said to be minimal if there does not exist any D '

   1. such that

      D' is a

      double dominating set of G . A double dominating set D , denoted by x 2 G , is said to be

      minimum, if it is minimal as well as it gives double domination number. Let

      G V , E ,V

      1, 2,…, N

      , V n,

   2. m be a connected interval graph in which the vertices are

   given in the sorted order of the right end points of the interval representation of the graph. Intervals are labeled according to increasing order of their endpoints. This labeling is referred to as an interval graph ordering. The purpose of this paper is to find the 2-tuple dominating set of an induced subgraph a non-split dominating set by introducing the Algorithm 2DIG [4,5].

2. MAIN THEOREMS

   1. Theorem

      If i and j are any two intervals in I such that

      i D, j

      1 and j is contained in i, if

      there is at least one interval to the left of j that intersect j and there is at at least one interval

      k i to the right of j that intersect j . Then non-split domination occurs in G and also the

      cardinality of the 2-tuple dominating set of the connected induced sub graph G1

      V D is

      D1 n 1.

      Proof:-

      Let I

      {i1,i2 ,…..,in }

      be the given interval family and G is an interval graph

      corresponding to I . Suppose there is at least one interval k i to the right of j that intersect j . Then it is obvious that j is adjacent to k in V D , so that there will not be any

      disconnection in V D , then G is a connected graph. Again we have to show that the cardinality of 2-tuple dominating set of an induced subgraph of non-split dominating set is

      D1 n

      1, where n

      7 . Infact the number of intervals I

      {1, 2,…..,10} . Next we will find the

      2-tuple dominating set of an induced subgraph V D by using an Algorithm 2DIG as follows:

   2. An algorithm for finding 2-tuple domination:-

      In a connected induced subgraph V D of G the vertices are ordered by an interval

      graph ordering. First of all we treat none of a vertex of V (G)

      is a member of dominating set

      D1 .

      Then insert vertices one by one by testing their consistency. If a vertex v is dominated by at least two vertices then leave it, otherwise take the highest numbered adjacent vertex (vertices) from

      N[v] as member(s) of dominating set

      D1 .

      Let us associate a new term

      Mi (v)

      for a vertex v V , for all i

      0,1, 2,….., k(k N (v) )

      to each adjacent vertices of v in order to an interval graph ordering of intervals as follows,

      i 1

      Mi (v) min

      N[v]

      M (v)

      i

      j 0

      With

      M 0 (v) min

      N (v)

      Basically,

      M 0 (v)

      L(v) , the lowest numbered adjacent vertex of v . In connection with

      the name of

      L(v)

      we call this

      Mi (v)

      as the p – th numbered adjacent vertex of

      v. Let u, v V .

      If for some

      i (i

      0,1, 2,….., N (v) ),

      N (v)

      i p such that

      1. M i (v) , then u is called the

         p – th numbered adjacent vertex of v .

   3. An algorithm 2DIG:

      Input: An interval graph G

      (V , E)

      with IG ordering vertex set V

      {1, 2,3,….., n}

      Output: 2-tuple dominating set

      D1 and 2-tuple domination number

      X 2 (G)(

      D1 )

      Step 1: Set

      f ( j) 0, j

      1, 2,….., n; // Assume that no vertices are the members of D1 .//

      Step 2: Set i

      1, D1

      and L .

      Step 2.1: Compute Wi ( f )

      1. N [i]

      f (v) ;

      Step 2.2: If Wi ( f ) 0 then // At least the vertex i not adjacent to any of the vertices of D1 //

      Set

      f (M m (i)) 1

      and

      f (Mm 1 (i)) 1;

      where m is the ending neighbourhood of i

      in the table of p – th numbered adjacent vertices.

      D1 D1

      {Mm (i)} {Mm 1 (i)} and L L

      {i};

      Else if Wi ( f ) 1 then // At least the vertex i is connected to one of the vertex of D1 .//

      If f (M m (i)) 1 then set

      f (Mm 1 (i)) 1; D1

      D1 {M m 1 (i)};

      Else Set D1

      f (M m (i)) 1;

      D1 {M m (i)};

      End if;

      L L

      Else

      {i};

      Go to Step 2.3; End if;

      Step 2.3: Calculate i i

      1 and go to Step 2.1 and continue until

      i n ;

      end 2DIG.

      An algorithm 2DIG gives the set

      D1 which is the minimum 2-tuple dominating set and

      D1 , the 2-tuple domination number of the interval graph G

      (V , E) . Here we denote the Set L

      as the set of leading vertices corresponding to the 2-tuple dominating set

      D1 .

      Now we will find the 2-tuple dominating set of an interval graph as follows an illustration,

      1 4 7 10

      2 6 8

      3 5 9

      Fig.1: Interval family I

      nbd [1] = {1,2,3}, nbd [2] = {1,2,3,4}, nbd [3] = {1,2,3,4,6}, nbd [4] = {2,3,4,5,6},

      nbd [5] = {4,5,6,7}, nbd [6] = {3,4,5,6,7,9}, nbd [7] = {5,6,7,8,9}, nbd [8] = {7,8,9,10},

      nbd [9] = {6,7,8,9,10}, nbd [10] = {8,9,10}

      We may constructed an interval graph G of I interms of neighbours, from G the dominating set DS = {3,7,10}

      9 2

      1

      4

      8

      6 5

      Fig.2: Vertex induced subgraph V D – Connected graph from G

      nbd [1] = {1,2}, nbd [2] = {1,2,4}, nbd [4] = {2,4,5,6},

      nbd [5] = {4,5,6}, nbd [6] = {4,5,6,9}, nbd [8] = {8,9}, nbd [9] = {6,8,9}

      To find the minimum 2-tuple dominating set, we have to compute all p – th numbered adjacent vertices.

      Mi v \ v	1	2	4	5	6	8	9
      M 0 v	1	1	2	4	4	8	6
      M1 v	2	2	4	5	5	9	8
      M 2 v	–	4	5	6	6	–	9
      M 3 v	–	–	6	–	9	–	–

      First set

      f ( j) 0,

      j V . In Step 2, set i

      1, D1

      and L , that is initially

      D1 and L

      are empty. Step 2 repeats for n times. Here n 7 , the number of vertices in the induced sub

      graph G1

      Iteration (1) :

      V D .

      Now we will illustrate the iterations in the following way:

      For the first iteration i 1

      N 1 1, 2

      w1 f f (N[1])

      w1 f f 1

      f 2 0

      The first condition of if-end if is satisfied. Since w1 f

      0, we find M1

      1 2, M 0 1 1

      Then set Also set

      f 1 1, f 2 1

      D1

      Iteration (2):

      1, 2

      D1 {1, 2}, L

      {1} i i 1 2

      For the second iteration i 2

      N 2 1, 2, 4,

      w2 f f (N[2])

      w1 f f 1 f 2

      f 4 1 1 0 2

      That is the vertex 2 is dominated by two vertices 1 and 2 of D1 . So, in this iteration D1

      could not be calculated. Hence

      Iteration (3)

      For the third iteration i

      D1 and L remains same and i is being increased to 3 .

      3

      N 4 2, 4, 5, 6

      w4 f f (N[4])

      w4 f f 2

      f 4 f (5)

      f (6) 1 0 0 0 1

      Here the domination criteria is not satisfied. The else- if condition of if-end if is satisfied.

      Now, we check either

      f (M 3 (4)) 1

      or not. We see that

      f (M3 (4))

      f (6) 0

      and hence set

      f (6) 1. Update D1

      by D1 {6} {1, 2, 6}

      and L by L

      {3} {1,3}.

      The iteration number i is

      being increased to 4 .

      Iteration (4):

      For the fourth iteration i 4

      N 5 4, 5, 6

      w5 f f (N[5])

      w5 f f 4

      f 5 f (6) 0 0 1 1

      Here also the domination criteria is not satisfied. Now, we check either We see that

      f (M 2 (5)) 1 or not.

      f (M 2 (5))

      f (6) 1 and hence set

      f (M1(5)) 1,

      i.e., f (5) 1, D1

      D1 {5} {1, 2,5, 6}, L L

      {4} {1,3, 4}.

      The iteration number i is being increased to 5 .

      Iteration (5):

      For the fifth iteration i 5

      N 6 4, 5, 6, 9

      W6 f f (N[6])

      W6 f f 4

      f 5 f 6

      f 9 0 1 1 0 2

      In this iteration

      Iteration (6):

      D1 and L remain unchanged. The iteration number i is being increased to 6 .

      For the sixth iteration i 6

      N 8 8, 9

      W8 ( f )

      f (N[8])

      W8 ( f ) f 8

      f 9 0 0 0

      The first condition of if-end if is satisfied.

      Since w8 f

      0, we find M1

      8 9, M 0

      8 8 .

      Then set f 8 1, f 9 1

      D1 {1, 2, 5, 6,8, 9}, L

      Iteration (7):

      {1, 3, 4, 6}

      For the seventh iteration i 7

      N 9 6,8, 9

      W9 f f (N[9])

      W9 f f 6

      f 8 f

      9 1 0 1 2

      In this iteration

      D1 and L remain unchanged.

      D1 1, 2, 5, 6,8, 9 , L

      {1, 3, 4, 6}

      D1

   4. Theorem

      Cardinality of D1

      6 .

      If i and j are any two intervals in I such that

      i D1, j

      1 and j is contained in i, if

      there one more interval other than i that intersect j, the induced subgraph V D is

      connected, then the cardinality of 2-tuple dominating set of V D is D1 n 3

      Proof:-

      Let I

      {i1,i2 ,…..,in }

      be the given interval family and G is an interval graph of I. Let

      j 1 be the interval contained in i , where i D . Suppose k is an interval, k i and k

      intersect j . Since i D , the induced sub graph V D does not contain i . Further in

      V D , the vertex j is adjacent to the vertex k and hence the graph G will not be

      disconnected in

      V D .

      Let

      G1 be an induced sub graph V D of G . Since

      {i1, i2 ,….., in }

      G and {i1, i3 , i4 , i5 , i6 , i8 , i9 , i10}

      G1 . Now we have to find the 2-tuple dominating set

      from the induced sub graph

      G1 . In this connection to find the 2-tuple dominating set we used an

      algorithm 2DIG as discussed in the Theorem 1.

      Now we will find the 2-tuple dominating set as follows an interval family,

      2 5 8

      1 4 6 10

      3 7 9

      Fig.1: Interval Family I

      nbd [1] = {1,2,3}, nbd [2] = {1,2,3,4}, nbd [3] = {1,2,3,4,5}, nbd [4] = {2,3,4,5,7},

      nbd [5] = {3,4,5,6,7}, nbd [6] = {5,6,7,8}, nbd [7] = {4,5,6,7,8,9,10}, nbd [8] = {6,7,8,9,10},

      nbd [9] = {7,8,9,10},nbd [10] = {7,8,9,10}

      Dominating set of an interval graph of G is DS {2,7}

      10 1

      9

      3

      8 4

      6 5

      Fig.2: Vertex induced graph V D – Connected graph

      nbd [1] ={1,3}, nbd [3] ={1,3,4,5}, nbd [4] ={3,4,5}, nbd [5] ={3,4,5,6}, nbd [6] ={5,6,8},

      nbd [8] ={6,8,9}, nbd [9] ={8,9}, nbd [10] ={8,9,10}

      To find the minimum 2-tuple dominating set, we have to compute all p – th numbered adjacent vertices as follows.

      Mi v \ v	1	3	4	5	6	8	9	10
      M 0 v	1	1	3	3	5	6	8	8
      M1 v	3	3	4	4	6	8	9	9
      M 2 v	–	4	5	5	8	9	–	10
      M 3 v	–	5	–	6	–	–	–	–

      First set

      f ( j) 0,

      j V . In Step 2, set i

      1, D1

      and L , that is initially

      D1 and L

      are empty. Step 2 repeats for n times. Here n 8 , the number of vertices in the induced sub

      graph G1

      V D .

      Now we will illustrate the iterations in the following way:

      Iteration (1) :

      For the first iteration i 1

      N 1 1, 3

      w1 f f (N[1])

      w1 f f 1

      f 3 0

      The first condition of if-end if is satisfied. Since

      w1 f

      0, we find

      M1 1 3, M 0 1 1

      Then set Also set

      f 1 1, f 3 1

      D1

      Iteration (2):

      1, 3

      D1 {1, 3}, L

      {1} ,i i 1 2

      For the second iteration i 2

      N 3 1, 3, 4, 5

      w3 f f (N[3])

      w3 f f 1 f 3 f 4

      f (5) 1 1 0 0 2

      That is the vertex 2 is dominated by two vertices 1 and 3 of D1 . So, in this iteration D1

      could not be calculated. Hence

      Iteration (3)

      For the third iteration i

      D1 and L remains same and i is being increased to 3 .

      3

      N 4 3, 4, 5

      w4 f f (N[4])

      w4 f f 3 f 4

      f (5) 1 0 0 1

      Here the domination criteria is not satisfied. The else- if condition of if-end if is satisfied.

      Now, we check either

      f (M 2 (4)) 1

      or not. We see that

      f (M 2 (4))

      f (5) 0

      and hence set

      f (5) 1. Update D1 by

      D1 {5} {1, 3, 5}

      and L by L

      {3} {1,3}.

      The iteration number i is

      being increased to 4 .

      Iteration (4):

      For the fourth iteration i 4

      N 5 3, 4, 5, 6

      w5 f f (N[5])

      w5 f f (3) f 4

      f 5 f (6) 1 0 1 0 2

      In this iteration

      D1 could not be calculated. Hence

      D1 and L remains same and i is being

      increased to 3 . The iteration number i is being increased to 5 .

      Iteration (5):

      For the fifth iteration i 5

      N 6 5, 6,8

      W6 f f (N[6])

      W6 f f 5 f 6

      f 8 1 0 0 1

      Here also the domination criteria is not satisfied. Now, we check either We see that

      f (M 2 (6)) 1 or not.

      f (M 2 (6))

      f (8) 1,

      f (8) 0 and hence set

      D1 D1

      {8} {1, 3, 5,8}, L L

      {5} {1, 3, 5}.

      The iteration number i is being increased to 6 .

      Iteration (6):

      For the sixth iteration i 6

      N 8 6,8, 9

      W8 ( f )

      f (N[8])

      W8 ( f )

      f (6) f 8

      f 9 0 1 0 1

      not.

      Here also the domination criteria is not satisfied. Now, we check either

      f (M 2 (8)) 1 or

      We see that

      f (M 2 (8))

      f (9) 1,

      f (9) 0

      and hence set

      D1 D1

      {9} {1, 3, 5,8, 9}, L L

      {6} {1, 3, 5, 6}.

      The iteration number i is being increased to 7 .

      Iteration (7):

      For the seventh iteration i 7

      N 9 8, 9

      W9 f f (N[9])

      W9 f f 8

      f 9 1 1 2

      In this iteration

      Iteration (8):

      D1 and L remain unchanged. The iteration number i is being increased to 8 .

      For the eighth iteration i 8

      N 10 8, 9,10

      W10

      f f (N[10])

      W10

      f f 8 f 9

      f (10) 1 1 0 2

      In this iteration

      D1 and L remain unchanged.

      D1 1, 3, 5,8, 9 , L

      {1, 3, 4, 6}

      D1

   5. Theorem

Cardinality of D1

5 .

Let I

{i1,i2 ,…..,in }

be an interval family and G be an interval graph of I . If i, j, k are

three consecutive intervals such that i j k and j D , i intersects j , j intersect k and i

intersect k then the induced sub graph V D is connected. Also the cardinality of 2-tuple

dominating set of V D is D1

Proof:-

n 3.

Let I

{i1,i2 ,…..,in } be an interval family and G be an interval graph of I . Let

i, j, k be

three consecutive intervals satisfy the hypothesis. Now i and k intersect implies that i and k are adjacent in V D . So that there will not be any disconnection in V D . Further we wil

find the 2-tuple dominating set of G1 . Since G1 is an induced subgraph. Now we will prove that

the cardinality of 2-tuple dominating set D1

in Theorem 1.

n 3 by using the Algorithm 2DIG as discussed

Now we will find the 2-tuple dominating set as follows, consider the following inter val family

2 5 8

11

1 4 7 10

3 6 9

Fig.1: Interval Family I

nbd [1] = {1,2,3}, nbd [2] = {1,2,3,4}, nbd [3] = {1,2,3,4,5}, nbd [4] = {2,3,4,5,6},

nbd [5] = {3,4,5,6,7}, nbd [6] = {4,5,6,7,8}, nbd [7] = {5,6,7,8,9}, nbd [8] = {6,7,8,9,10,11},

nbd [9] = {7,8,9,10,11}, nbd [10] = {8,9,10,11}, nbd [11] = {8,9,10,11}

Dominating set of the interval graph is D

{3,8}

11 1

10

2

4

9

7

Fig.2: Vertex induced graph

5

6

V D – Connected graph

nbd [1] ={1,2}, nbd [2] ={1,2,4}, nbd [4] ={2,4,5,6}, nbd [5] ={4,5,6,7}, nbd [6] ={4,5,6,7},

nbd [7] ={5,6,7,9}, nbd [9] ={7,9,10,11}, nbd [10] ={9,10,11}, nbd [11] = {9,10,11}

To find the minimum 2-tuple dominating set, we have to compute all p – th numbered adjacent vertices follows.

First set

f ( j) 0,

j V . In Step 2, set i

1, D1

and L , that is initially

D1 and L

are empty. Step 2 repeats for n times. Here n 9 , the number of vertices in the induced sub

graph G1

V D .

Now we will illustrate the iterations in the following way:

Iteration (1) :

For the first iteration i 1

N 1 1, 2

w1 f f (N[1])

w1 f f 1

f 2 0

The first condition of if-end if is satisfied. Since

w1 f

0, we find

M1 1 2, M 0

1 1 . Then set

f 1 1, f 2 1

Also set

D1

Iteration (2):

1, 2

D1 {1, 2}, L

{1} ,i i 1 2

For the second iteration i 2

N 2 1, 2, 4

w2 f f (N[2])

w2 f f 1 f 2

f 4 1 1 0 2

That is the vertex 2 is dominated by two vertices 1 and 2 of D1 . So, in this iteration D1

could not be calculated. Hence

Iteration (3)

For the third iteration i

D1 and L remains same and i is being increased to 3 .

3

N 4 2, 4, 5, 6

w4 f f (N[4])

w4 f f 2

f 4 f (5)

f (6) 1 0 0 0 1 Here the domination criteria is not

satisfied. The else- if condition of if-end if is satisfied. Now, we check either

f (M 3 (4)) 1 or

not. We see that

f (M3 (4))

f (6) 0

and hence set

f (6) 1. Update D1

by D1 {6} {1, 2, 6}

and L by L {3} {1,3}. The iteration number i is being increased to 4 .

Iteration (4):

For the fourth iteration i 4

N 5 4, 5, 6, 7

w5 f f (N[5])

w5 f f 4

f 5 f (6)

f (7) 0 0 1 0 1

Here also the domination criteria is not satisfied. Now, we check either We see that

f (M 3 (5)) 1 or not.

f (M3 (5))

f (7) 0

and hence set

f (7) 1, D1

D1 {7} {1, 2, 6, 7}, L L

{4} {1,3, 4}.

The iteration number i is being increased to 5 .

Iteration (5):

For the fifth iteration i

5, N

6 4, 5, 6, 7

W6 f f (N[6]),W6

f f (4) f 5 f 6

f 7 0 0 1 1 2

In this iteration

D1 could not be calculated. Hence

D1 and L remains same. The iteration number

i is being increased to 6 .

Iteration (6):

For the sixth iteration i 6

N 7 5, 6, 7, 9

W7 ( f )

f (N[7])

W7 ( f )

f (5)

f (6) f 7

f 9 0 1 1 0 2

In this iteration

D1 could not be calculated. Hence

D1 and L remains same. The iteration number

i is being increased to 7 .

Iteration (7):

For the seventh iteration i 7

N 9 7, 9,10,11

W9 f f (N[9])

W9 f f (7) f 9

f 10

f (11) 1 0 0 0 1

Here also the domination criteria is not satisfied. Now, we check either We see that

f (M 3 (9)) 1 or not.

f (M3 (9))

f (11) 1,

f (11) 0

and hence set

D1 D1

{11} {1, 2, 6, 7,11}, L L

{7} {1, 3, 4, 7}.

The iteration number i is being increased to 8 .

Iteration (8):

For the eighth iteration i 8

N 10 9,10,11

W10

f f (N[10])

W10

f f 9

f (10)

f (11) 0 0 1 1

Here also the domination criteria is not satisfied. Now, we check either We see that

f (M 2 (10)) 1 or not.

f (M 2 (10))

f (M1(10))

f (11) 1 and hence set

f (10) 1,

D1 D1

{10} {1, 2, 6, 7,10,11}, L L

{8} {1,3, 4, 7,8}.

The iteration number i is being increased to 9 .

Iteration 9:

For the ninth iteration i 9

N 11 9,10,11

W11 ( f )

f (N[11])

W11 ( f )

f (9)

f (10)

f 11 0 1 1 2

In this iteration

D1 could not be calculated. Hence

D1 and L remains same.

D1 1, 2, 6, 7,10,11 , L

{1, 3, 4, 7,8}

D1 Cardinality of D1 6

1. E. Sampath Kumar, P.S. Neeralagi, The neighbourhood of graph, Indian J.Pure.Appl.Math., 16,1985, 126-132.

2. V.R. K ulli, S.K. Sigarkant, Further results on a neighbourhood number of graph, Indian J. Pure.Appl.Math., 23,1992,575-577.

3. V.R. Kulli, B. Janakiram, The Non-split domination number of a graph, Indian J. Pure. Applied Mathematics, Vol.31(5), 545-550, May 2000.

4. M. Pal, S. Mondal, D. Bera and T.K. Pal, An optimal parallel algorithm for computing cutvertices and blocks on interval graphs, International Journal of Computer Mathematics, 75 (2000) 59-70.

5. M.C. Golumbic, Algorithmic Graph Theory and Perfect Graphs, Academic Press, New York, 1980.

6. F. Harary and T.W.Haynes, Double domination in graphs, Ars Combination, 55 (2000) 201-213.

7. T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Domination in Graphs: Advanced Topics,

Marcel Dekker. Inc. New York. 1998.