 Open Access
 Total Downloads : 820
 Authors : Dr.A.Sudhakaraiah, E. Gnana Deepika, V. Rama Latha
 Paper ID : IJERTV1IS3054
 Volume & Issue : Volume 01, Issue 03 (May 2012)
 Published (First Online): 30052012
 ISSN (Online) : 22780181
 Publisher Name : IJERT
 License: This work is licensed under a Creative Commons Attribution 4.0 International License
To Find A 2Tuple Dominating Set of an Induced Subgraph of a NonSplit Dominating Set of an Interval Graph Using an Algorithm
TO FIND A 2TUPLE 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, Tirupati517502, 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 nonsplit dominating set, if the induced subgraph V D is
connected. The nonsplit dominating number
ns (G)
of G is the minimum cardinality of a non
split dominating set. The 2tuple 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 2tuple dominating set of an induced subgraph of a nonsplit dominating set of an interval graph.
Key Words: Interval family, Interval graph, connected graph, Dominating Set, Nonsplit dominating set, 2tuple domination, design of an algorithm.

INTRODUCTION
An undirected graph G
(V , E) is an interval graph(IG), if the vertex set V can be put
into onetoone 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 nonempty 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 nonsplit
dominating set if the induced sub graph V D is connected. The nonsplit domination
number
ns (G)
of G is the minimum cardinality of a nonsplit 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 '

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,

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 2tuple dominating set of an induced subgraph a nonsplit dominating set by introducing the Algorithm 2DIG [4,5].


MAIN THEOREMS

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 nonsplit domination occurs in G and also the
cardinality of the 2tuple 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 2tuple dominating set of an induced subgraph of nonsplit dominating set is
D1 n
1, where n
7 . Infact the number of intervals I
{1, 2,…..,10} . Next we will find the
2tuple dominating set of an induced subgraph V D by using an Algorithm 2DIG as follows:

An algorithm for finding 2tuple 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

M i (v) , then u is called the
p – th numbered adjacent vertex of v .


An algorithm 2DIG:
Input: An interval graph G
(V , E)
with IG ordering vertex set V
{1, 2,3,….., n}
Output: 2tuple dominating set
D1 and 2tuple 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 )

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 2tuple dominating set and
D1 , the 2tuple domination number of the interval graph G
(V , E) . Here we denote the Set L
as the set of leading vertices corresponding to the 2tuple dominating set
D1 .
Now we will find the 2tuple 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 2tuple 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 ifend 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 ifend 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 ifend 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


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 2tuple 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 2tuple dominating set
from the induced sub graph
G1 . In this connection to find the 2tuple dominating set we used an
algorithm 2DIG as discussed in the Theorem 1.
Now we will find the 2tuple 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 2tuple 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 ifend 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 ifend 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

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 2tuple
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 2tuple dominating set of G1 . Since G1 is an induced subgraph. Now we will prove that
the cardinality of 2tuple dominating set D1
in Theorem 1.
n 3 by using the Algorithm 2DIG as discussed
Now we will find the 2tuple 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 2tuple dominating set, we have to compute all p – th numbered adjacent vertices follows.
Mi v \ v 
1 
2 
4 
5 
6 
7 
9 
10 
11 
M 0 v 
1 
1 
2 
4 
4 
5 
7 
9 
9 
M1 v 
2 
2 
4 
5 
5 
6 
9 
10 
10 
M 2 v 
– 
4 
5 
6 
6 
7 
10 
11 
11 
M 3 v 
– 
– 
6 
7 
7 
9 
11 
– 
– 
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 ifend 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 ifend 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

E. Sampath Kumar, P.S. Neeralagi, The neighbourhood of graph, Indian J.Pure.Appl.Math., 16,1985, 126132.

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

V.R. Kulli, B. Janakiram, The Nonsplit domination number of a graph, Indian J. Pure. Applied Mathematics, Vol.31(5), 545550, May 2000.

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) 5970.

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

F. Harary and T.W.Haynes, Double domination in graphs, Ars Combination, 55 (2000) 201213.

T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Domination in Graphs: Advanced Topics,
Marcel Dekker. Inc. New York. 1998.