# Minimum 2-Tuple Dominating Set of an Interval Graph

Authors: Tarasankar Pramanik; Sukumar Mondal; Madhumangal Pal
Journal: International Journal of Combinatorics
 (2011)

---

## Abstract

Thek-tuple domination problem, for a fixed positive integer k, is to find a minimum size vertex subset such that every vertex in the graph is dominated by at least k vertices in this set. The case when k=2 is called 2-tuple domination problem or double domination problem. In this paper, the 2-tuple domination problem is studied on interval graphs from an algorithmic point of view, which takes O(n2) time, n is the total number of vertices of the interval graph.


---

## Body

## 1. Introduction

An undirected graphG=(V,E) is an interval graph 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 nonempty intersection. The set I is called an interval representation of G and G is referred to as the intersection graph of I [1]. Let I={i1,i2,…,in}, where ic=[ac,bc] for 1≤c≤n, be the interval representation of the graph G, ac is the left endpoint, and bc is the right end point of the interval ic. Without any loss of generality, assume the following:(a)
an interval contains both its endpoints and that no two intervals share a common endpoint [1],(b)
intervals and vertices of an interval graph are one and the same thing,(c)
the graphG is connected, and the list of sorted endpoints is given(d)
the intervals inI are indexed by increasing right endpoints, that is, b1<b2<⋯<bn.In a graphG, 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. For a fixed positive integer k, a k-tuple dominating set of G=(V,E) is a subset D of V such that every vertex in V is dominated by at least k vertices of D. As introduced by Harary and Haynes [2], a k-tuple dominating setD is a set D⊆V for which |N[v]∩D|≥k for every v∈V, where N[v]={v}∪{u∈V:(u,v)∈E} is the closed neighborhood of the vertex v. Note that we must have the minimum degree greater than or equal to k-1 for a k-tuple dominating set to exist. The k-tuple domination numberγ×k(G) is the minimum cardinality of k-tuple dominating set of G. When k=2, this is called double domination [3].A 2-tuple dominating setD is said to be minimalif there does not exist any D′⊂D such that D′ is a 2-tuple dominating set of G. A 2-tuple dominating set D, denoted by γ×2(G), is said to be minimum, if it is minimal as well as it gives 2-tuple domination number.In graph theory, a connected component of an undirected graph is a subgraph in which any two vertices are connected to each other by paths. For a graphG, 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 subgraph is called its component. Removal of a vertex v from a graph G means the removal of vertex v and edges incident to v. A cut vertex of a connected graph G is a vertex of G whose removal renders G disconnected. Pal et al. [4] described an algorithm for computing cut vertices and blocks on interval graphs.A graphG is vertex domination-critical if for any vertex v of G, the domination number of G-v is less than the domination number of G. If such a graph G has domination number γ, it is called γ-critical. Brigham et al. [5] studied γ-critical graphs and posed the following questions.(1)
IfG is a γ-critical graph, is |V|≥(δ+1)(γ-1)+1?(2)
If aγ-critical graph G has (Δ+1)(γ-1)+1 vertices, is G regular?(3)
Doesi=γ for all γ-critical graphs?(4)
Letd be the diameter of the γ-critical graph G. Does d≤2(γ-1) always hold?Later in this paper, it has been proved that for some vertex (or cut vertex)v of G, G-v and G have the same domination number γ×2(G).


### 1.1. Survey of Related Works

Various works have been found on interval graphs. Interval graphs are useful in modeling resource allocation problems in operations research.  A. Pal and M. Pal [6] have studied about interval graphs. So many algorithms and results of various parameters on interval graphs have been found in [4, 7–12]. The domination is one of the parameters in graphs which has a great importance in modern circuit designing systems. Chang et al. [13] have extensively studied about domination in graphs. Also domination and its variations can be found in [14–17]. Another type of dominating set has been widely studied in [18] which is a total dominating set. Henning has worked on graphs with large total domination number in [19]. For a domination number, Sumner and Blitch [20] studied graphs where the addition of any edge changed the domination number. They called graphs with this property domination edge critical. Brigham et al. [5] and Fulman et al. [21] have worked on vertex domination-critical graphs. Wojcicka [22] have found some results on Hamiltonian properties of domination-critical graphs. The total domination edge critical graphs, that is, graphs where the addition of any edge decreased the total domination number were studied by Haynes et al. in [23–26]. Among the variations of domination, the k-tuple domination was introduced in [3]. The case when k=2 was called double domination in [3], where exact values of the double domination numbers for some special graphs are obtained. In the same paper, various bounds of double and k-tuple domination numbers are available in terms of the other parameters.


## 1.1. Survey of Related Works

Various works have been found on interval graphs. Interval graphs are useful in modeling resource allocation problems in operations research.  A. Pal and M. Pal [6] have studied about interval graphs. So many algorithms and results of various parameters on interval graphs have been found in [4, 7–12]. The domination is one of the parameters in graphs which has a great importance in modern circuit designing systems. Chang et al. [13] have extensively studied about domination in graphs. Also domination and its variations can be found in [14–17]. Another type of dominating set has been widely studied in [18] which is a total dominating set. Henning has worked on graphs with large total domination number in [19]. For a domination number, Sumner and Blitch [20] studied graphs where the addition of any edge changed the domination number. They called graphs with this property domination edge critical. Brigham et al. [5] and Fulman et al. [21] have worked on vertex domination-critical graphs. Wojcicka [22] have found some results on Hamiltonian properties of domination-critical graphs. The total domination edge critical graphs, that is, graphs where the addition of any edge decreased the total domination number were studied by Haynes et al. in [23–26]. Among the variations of domination, the k-tuple domination was introduced in [3]. The case when k=2 was called double domination in [3], where exact values of the double domination numbers for some special graphs are obtained. In the same paper, various bounds of double and k-tuple domination numbers are available in terms of the other parameters.


## 2. Interval Graph and Some of Its Properties

LetG=(V,E), V={1,2,…,n}, |V|=n, |E|=m be a connected interval graph in which the vertices are given in the sorted order of the right endpoints of the interval representation of the graph. Intervals are labeled according to increasing order of their endpoints. This labeling is referred to as IG ordering. Let (u,v) or (v,u) denote the existence of an adjacency relation between two vertices u, v. It is assumed that (u,u) is always true, that is, (u,u)∈E. If [au,bu] and [av,bv] are two end points of the vertices u and v, respectively, then u,v are adjacent if at least one of the following conditions hold:(i)
av<au<bv,(ii)
av<bu<bv,(iii)
au<av<bu,(iv)
au<bv<bu.The following lemma is true for a given interval graph,G=(V,E).Lemma 2.1 (see [27]).
If the verticesu,v,w∈V are such that  u<v<w in the IG ordering and  u is adjacent to  w, then  v is also adjacent to  w.For each vertexv∈V, let H(v) represent the highest numbered adjacent vertex of v. If no adjacent vertex of v exists with higher IG number than v, then H(v) is assumed to be v. In other words, H(v)=max{u:(v,u)∈E,u≥v}.Throughout this paper, we use the notationD for 2-tuple dominating set. For the purpose to find D of the interval graph G=(V,E), we consider a function f:V(G)→{0,1} which is defined by f(v)=1 if v∈D, otherwise, f(v)=0. We define the function f so that for S⊆V(G), f(S)=∑v∈Sf(v). The weight of the function f is w(f)=f(V(G)). Also, wi(f) is defined as wi(f)=f(N[i])=∑v∈N[i]f(v), for all i=1,2,3,…,n.


## 3. Algorithm for 2-Tuple Domination

In a connected interval graph, the vertices are ordered by IG ordering. First of all, we treat none of a vertex ofV(G) as a member of dominating set D. 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 D.Let us associate a new termMi(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 set IG ordering of intervals in the following way:(3.1)Mi(v)=max⁡{N[v]-⋃j=0i-1Mi(v)}withM0(v)=max⁡{N[v]}.Basically,M0(v)=H(v), the highest numbered adjacent vertex of v [28]. In connection with the name of H(v), we call this Mi(v) as the pthnumbered adjacent vertex ofv through Definition 3.1.Definition 3.1 (pth numbered adjacent vertex).
Letu,v∈V.If for some i(i=0,1,2,…,|N(v)|), |N(v)|-i=p such that u=Mi(v), then u is called the pth numbered adjacent vertex of v.From the definition, it is easily seen that, for a vertexv, Mi(v) exists for maximum possible i=|N(v)|, that is, degree of the vertex v. Therefore, in a graph, the maximum possible i occurs in the degree of the graph, that is, Δ=max{deg(v):v∈V}. An illustration of the computations of all Mi(v) for the graph of Figure 1 are shown in Table 1.Table 1
Computation of allpth numbered adjacent vertices.
Mi(v)v12345678910M0(v)5558888101010M1(v)4445677899M2(v)12345667—8M3(v)———345—6——M4(v)———23——5——M5(v)———12——4——M6(v)————1—————Figure 1
An interval graphG=(V,E).Now, we describe an algorithm to find two sets of verticesD and L depending only on M0(i) and M1(i).Actually, the Algorithm  2DIG (Algorithm1) gives the set D which is the minimum 2-tuple dominating set and |D|, the 2-tuple domination number of the interval graph G=(V,E). Before going to prove this result, we first verify Algorithm  2DIG in Figure 2. Here, we denote the set L as the set of leading vertices corresponding to the 2-tuple dominating set D.Algorithm 1:Algorithm  2DIG.
Input: An interval graph G=(V,E) with IG ordering vertex set V={1,2,3,…,n}.Output: 2-tuple dominating set D and 2-tuple domination number γ×2(G)(=|D|).Step  1: Set f(j)=0,∀j=1,2,…,n; //Assume that no vertices are the membersofD.//Step  2: Set i=1, D=∅ and L=∅;Step  2.1: Compute wi(f)=∑v∈N[i]f(v);Step  2.2: If wi(f)=0 then //At least the vertex i is not adjacent to any of thevertices of D.//Set f(M0(i))=1 and f(M1(i))=1;D=D∪{M0(i)}∪{M1(i)} and L=L∪{i};else if wi(f)=1 then //At least the vertex i is connected to one of thevertex of D.//If f(M0(i))=1 thenSet f(M1(i))=1;D=D∪{M1(i)};elseSetf(M0(i))=1;D=D∪{M0(i)};end if;L=L∪{i};elseGoto 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.Figure 2
An interval representation of Figure1.In Algorithm  2DIG, atith iteration, if wi(f)=0, then i is a member of L and i is said to be the leading vertex of order2 corresponding to the vertices M0(i) and M1(i) of D, and if wi(f)=1, then i is said to be the leading vertex of order1 corresponding to the vertex M0(i) or M1(i) of D, otherwise, i does not belong to L.Therefore, we conclude that ifl1∈L, then l1 is adjacent to exactly two vertices of D.


### 3.1. Verification of the Algorithm

Suppose we are to find 2-tuple dominating setD and 2-tuple domination number |D| of the interval graph G=(V,E), where V={1,2,…,10} shown in Figure 1. First, set f(j)=0, for all j∈V. In Step  2, set i=1, D=∅ and L=∅, that is, initially D and L are empty. Step  2 repeats for n times. Here, n=10, number of vertices in the graph. We illustrate the iterations in the following way.Iteration 1.
For the first iterationi=1, N[1]={1,4,5}. Calculate w1(f)=f(1)+f(4)+f(5)=0. The first condition of if-end if is satisfied. Since w1(f)=0, we find M0(1)=5 and M1(1)=4. Then, set f(5)=1 and f(4)=1. Also, set D=∅∪{4,5}={4,5}, L={1}, and i=i+1=2.Iteration 2.
N[2]={2,4,5}. w2(f)=f(N[2])=2. The vertex 2 is dominated by two vertices 4 and 5 of D. So, in this iteration, D could not be calculated. Hence, D and L remain the same and i is being increased to 3.Iteration 3.
N[3]={3,4,5}. w3(f)=f(N[3])=2. In this iteration, also D and L remain unchanged. The iteration number i is being increased to 4.Iteration 4.
Here,N[4]={1,2,3,4,5,8} and w4(f)=f(N[4])=2. So, D and L are the same as the previous iteration. Set i=5.Iteration 5.
In this iteration,N[5]={1,2,3,4,5,6,8} and w5(f)=f(N[5])=2, and hence no change occurs. i is being increased to 6.Iteration 6.
N[6]={5,6,7,8} and w6(f)=f(N[6])=1. So, domination criteria are not satisfied here. The else-if condition of if-end if is satisfied. Now, we check either f(M0(6))=1 or not. We see that f(M0(6))=f(8)=0, and hence set f(8)=1. Update D by D∪{8}={4,5,8} and L by L∪{6}={1,6}. i is being increased to 7.Iteration 7.
N[7]={6,7,8} and w7(f)=f(N[7])=1. Here, also domination criteria are not satisfied. As f(M0(7))=f(8)=1, set f(M1(7))=f(7)=1 and D=D∪{7}={4,5,8,7} with L=L∪{7}={1,6,7}. i is being increased to 8.Iteration 8.
In this iteration, that is, fori=8, N[8]={4,5,6,7,8,10}. w8(f)=4. Hence, D and L remain unchanged and i is being increased to 9.Iteration 9.
At ninth iteration,i=9. Here, N[9]={9,10}w9(f)=0. Then, D=D∪{9,10}={4,5,8,7,9,10} and L=L∪{9}={1,6,7,9} with f(9)=1 and f(10)=1. Set i=10.Iteration 10.
Fori=10, N[10]={8,9,10}w10(f)=3. Hence, D and L remain unchanged. As there are 10 vertices in Figure 3, so, this is the last iteration.Figure 3
FindingD by Algorithm  2DIG.So, by the Algorithm  2DIG, we getD={4,5,8,7,9,10}, that is, D={4,5,7,8,9,10} and L={1,6,7,9}. Therefore, |D|= cardinality of D=6. In Figure 3, thick lines represent the members of D.


## 3.1. Verification of the Algorithm

Suppose we are to find 2-tuple dominating setD and 2-tuple domination number |D| of the interval graph G=(V,E), where V={1,2,…,10} shown in Figure 1. First, set f(j)=0, for all j∈V. In Step  2, set i=1, D=∅ and L=∅, that is, initially D and L are empty. Step  2 repeats for n times. Here, n=10, number of vertices in the graph. We illustrate the iterations in the following way.Iteration 1.
For the first iterationi=1, N[1]={1,4,5}. Calculate w1(f)=f(1)+f(4)+f(5)=0. The first condition of if-end if is satisfied. Since w1(f)=0, we find M0(1)=5 and M1(1)=4. Then, set f(5)=1 and f(4)=1. Also, set D=∅∪{4,5}={4,5}, L={1}, and i=i+1=2.Iteration 2.
N[2]={2,4,5}. w2(f)=f(N[2])=2. The vertex 2 is dominated by two vertices 4 and 5 of D. So, in this iteration, D could not be calculated. Hence, D and L remain the same and i is being increased to 3.Iteration 3.
N[3]={3,4,5}. w3(f)=f(N[3])=2. In this iteration, also D and L remain unchanged. The iteration number i is being increased to 4.Iteration 4.
Here,N[4]={1,2,3,4,5,8} and w4(f)=f(N[4])=2. So, D and L are the same as the previous iteration. Set i=5.Iteration 5.
In this iteration,N[5]={1,2,3,4,5,6,8} and w5(f)=f(N[5])=2, and hence no change occurs. i is being increased to 6.Iteration 6.
N[6]={5,6,7,8} and w6(f)=f(N[6])=1. So, domination criteria are not satisfied here. The else-if condition of if-end if is satisfied. Now, we check either f(M0(6))=1 or not. We see that f(M0(6))=f(8)=0, and hence set f(8)=1. Update D by D∪{8}={4,5,8} and L by L∪{6}={1,6}. i is being increased to 7.Iteration 7.
N[7]={6,7,8} and w7(f)=f(N[7])=1. Here, also domination criteria are not satisfied. As f(M0(7))=f(8)=1, set f(M1(7))=f(7)=1 and D=D∪{7}={4,5,8,7} with L=L∪{7}={1,6,7}. i is being increased to 8.Iteration 8.
In this iteration, that is, fori=8, N[8]={4,5,6,7,8,10}. w8(f)=4. Hence, D and L remain unchanged and i is being increased to 9.Iteration 9.
At ninth iteration,i=9. Here, N[9]={9,10}w9(f)=0. Then, D=D∪{9,10}={4,5,8,7,9,10} and L=L∪{9}={1,6,7,9} with f(9)=1 and f(10)=1. Set i=10.Iteration 10.
Fori=10, N[10]={8,9,10}w10(f)=3. Hence, D and L remain unchanged. As there are 10 vertices in Figure 3, so, this is the last iteration.Figure 3
FindingD by Algorithm  2DIG.So, by the Algorithm  2DIG, we getD={4,5,8,7,9,10}, that is, D={4,5,7,8,9,10} and L={1,6,7,9}. Therefore, |D|= cardinality of D=6. In Figure 3, thick lines represent the members of D.


## 4. Proof of Correctness and Time Complexity

Here, we will prove thatD is a minimum 2-tuple dominating set.Theorem 4.1.
The setD is a minimal 2-tuple dominating set.Proof.
LetD={d1,d2,…,dk} be the 2-tuple dominating set obtained by Algorithm  2DIG. We are to prove that this D is minimal 2-tuple dominating set, that is, there does not exist any D′⊂D such that D′ is a 2-tuple dominating set.
Suppose, there exists aD′⊂D such that D′ is a 2-tuple dominating set. Since D′⊂D, there must exist at least one member of D, say di, such that di∉D′. Let the leading vertex corresponding to di be k, then wk(f)=2. Again, since D′ is a 2-tuple dominating set and di∉D′, f(di)=0 and wk(f)=1 with respect to the 2-tuple dominating set D′. Therefore, k is dominated by only one vertex of D′, which is a contradiction of our assumption that D′ is a 2-tuple dominating set. Thus, D is minimal 2-tuple dominating set.Theorem 4.2.
The 2-tuple domination number of the given interval graph is the cardinality of the 2-tuple dominating setD, that is,  γ×2(G)=|D|.Proof.
LetL be the set of leading vertices corresponding to the minimal 2-tuple dominating set D of G. Suppose there exists another minimal 2-tuple dominating set D′ such that |D′|<|D|.
Without loss of generality, we assume thatl1 is the leading vertex of order 2 corresponding to the two vertices d1 and d2 of D. Then, l1 is adjacent to exactly two vertices d1, d2 (d1<d2) of D. Also d2=M0(l1), the highest numbered adjacent vertex to l1. So, there does not exist any vertex v>d2 in V such that l1 is adjacent to v. If d1,d2∉D′, then there exist at least two vertices, say, d1′,d2′∈D′ such that d1′<d2′<d1<d2, where each d1′ and d2′ are adjacent to l1. If |D|=2, then we have |D′|=2. So, γ×2(G)=|D′|=|D|. For |D|>2, consider the following two cases.Case 1.
Letl2 be the leading vertex of order 1 corresponding to a vertex d3∈D. Since l2 is of order 1, either d3=M0(l2) or d3=M1(l2) (by Algorithm  2DIG) and l2 is adjacent to d2 but not adjacent to d1. If l2 is adjacent to d1, then l2 is adjacent to three vertices d1,d2, and d3 of D (not exactly two), a contradiction. Hence, l2 is not adjacent to the vertices d1′ and d2′. As, (d1′,l2)∈E or (d2′,l2)∈E implies (d1,l2)∈E. Therefore, l2∈V is not dominated by at least two vertices of D′ and hence there exist at least two vertices d3′,d4′∈D′, where each d3′ and d4′ are adjacent to l2. Hence, |D′|≥|D|.Case 2.
Letl2 be the leading vertex of order 2 corresponding to the vertices d3,d4∈D(d3<d4). Then, l2 is not adjacent to any vertex higher than d4. Also, l2 is not adjacent to d1′ and d2′ as l2 is not adjacent to d2. Therefore, if D′ is a 2-tuple dominating set, l2 must be dominated by at least two vertices of D′, say d3′ and d4′. Hence, |D′|≥|D|.Thus, there does not exist any D′ such that |D′|<|D|, that is, D is minimum and hence γ×2(G)=|D|.Henceforth,D means the minimum 2-tuple dominating set and L is the set of leading vertices corresponding to D.Theorem 4.3.
The 2-tuple dominating set of an interval graph can be computed sequentially inO(n2) time.Proof.
Let the processor take unit time to perform a single instruction. Step  1 of Algorithm  2DIG takesO(n) time. The algorithm consists of a loop from Step  2.1 to Step  2.3. This loop carry over n times. Within this loop, we see that a loop occurs, which is terminated after O(|N[i]|) times. It is clear that |N[i]|≤p≤n, p is the upper bound of |N[i]|, for fixed i. In the worst case, we assume the loop runs over n times. So the total time complexity of Step  2 is O(n2). Hence, the overall time complexity of the Algorithm  2DIG is of O(n2).


## 5. Some Important Results Related to Minimum 2-Tuple Domination

In this section, we present some important results related to minimum 2-tuple domination on interval graphs. For a given interval graphG, let a tree T(G)=(V,E′) be defined such that E′={(u,H(u)):u∈V,u≠n},let n be the root of T(G). This tree is called the interval tree. The various properties of interval tree are available in [6, 10, 28].The following lemma is true for every connected interval graph.Lemma 5.1 (see [28]).
For a connected interval graph, there exists a unique interval treeT(G).For each vertexv of interval tree, level(v) is the distance of v from the vertex n in the tree. The height h of the tree T(G) is defined by (5.1)h=max⁡{level(v):v∈V}.We have found a result for the minimum 2-tuple dominating setD in terms of the height h of interval tree T(G) stated as follows.Lemma 5.2.
LetT(G) be the interval tree of the interval graph  G with height  h, then
(5.2)|D|≥{2⌈h3⌉,whereh≠3mforsomem∈N,2(h3+1),whereh=3mforsomem∈N,
where ℕ is the set of natural numbers.Proof.
From the definition of interval treeT(G), we know that the vertex 1 of V is at level h. By the property of interval tree T(G), we know that any vertex at level l is not adjacent with a vertex at level l-2 and level(u)≥level(v), for every u<v, u,v∈V [8]. Therefore, it is clear that the neighbors of the vertex v of level l are either at level l or at level l-1.
LetD={v1,v2,…,vk} such that v1<v2<⋯<vk. As the vertices at level h are not adjacent with the vertices at level h-2 or at level greater than h-2, two vertices v1, v2 of D must be taken from the level h or h-1. For the least possible D, we assume that v2 is at level h-1 and consequently v3 is either at level h-1 or h-2 or h-3. If v2 is at level h, then possibility of having v3 is either at h or at h-1 or at h-2 which decreases the level from earlier level and hence the number of vertices of D may increase. So this last case is excluded from our result as the result demands the lower bound of D. Also, in further cases, we neglect such cases for the same reason. Thus, we take v3 at level h-3, v4 at level h-4, v5 at level h-6, v6 at level h-7, v7 at level h-9, and so on. That is, v2k+1 at level h-3k and v2k+2 at level h-3k-1, for k=0,1,2,3,…. So for each k there are two vertices from the consecutive levels h-3k and h-3k-1.
Now, ifh=3m, for some m∈ℕ, then h-3k is the last level, that is, level 0 of T(G).
So,(5.3)h-3k=0,this givesk=h3.
Thus, there are ((h/3)+1) consecutive levels and hence the least value of |D| is 2((h/3)+1). If h≠3m, for some m∈ℕ, then h-3k is not at the last level of T(G). So one vertex is required at level h-3k-1 or h-3k-2. In this case, k=⌈h/3⌉-1. So there are 2⌈h/3⌉ consecutive levels and hence the least value of |D| is 2⌈h/3⌉.
Therefore,(5.4)|D|≥{2⌈h3⌉,whereh≠3mfor somem∈N,2(h3+1),whereh=3mfor somem∈N.Here, we are going to prove a result that removal of a vertexv from graph G, G-v and G have the same minimum 2-tuple dominating set D.Lemma 5.3.
Letv∉L∪D and  G′=(V′,E′), where  V′=V-{v} and  E′={(i,j)∈E:i∈V′,j∈V′}. Then  (i)
the minimum 2-tuple dominating set ofG′ and G is D, if G′ is connected,(ii)
ifG′ is disconnected with k components (blocks), say, G1,G2,…,Gk, then there must exist minimum 2-tuple dominating sets D1,D2,…,Dk of G1,G2,…,Gk such that D=D1∪D2∪⋯∪Dk and Di’s are pairwise disjoint.Proof.
(i) SupposeG′ is connected. Since, v∉L∪D, that is, v∈V-L∪D. By Algorithm  2DIG, at kth iteration, say, either if or else-if condition is satisfied for a vertex k of V, then k∈L∪D, otherwise, k∈V-L∪D. In this case, v∈V-L∪D, at v-th iteration, else condition is satisfied for the vertex v which has no effect on L and D. Hence, if the vertex is being deleted from the graph G, then the new induced subgraph G′=G-{v} has the same 2-tuple dominating set D as G.
(ii) LetG′ be disconnected and G′=G1∪G2∪⋯∪Gk, where G1=(V1,E1), G2=(V2,E2),…,Gk=(Vk,Ek). Let us decompose D into disjoint subsets D1,D2,…,Dk such that D1⊆V1, D2⊆V2,…,Dk⊆Vk, where V=V1∪V2∪⋯Vk∪{v}, that is, D=D1∪D2∪⋯∪Dk. As D is obtained by Algorithm  2DIG and v has no effect on D, then v has no effect on D1,D2,…,Dk, and they are also obtained by Algorithm  2DIG. Therefore, D1,D2,…,Dk are minimum 2-tuple dominating sets of interval graphs G1,G2,…,Gk, respectively.The generalized form of the Lemma5.3 is as follows.Corollary 5.4.
LetS={v∈V:v∉L∪D} and  G′=(V′,E′), where  V′=V-S and  E′={(i,j)∈E:i∈V′,j∈V′}. Then  (i)
the minimum 2-tuple dominating set ofG′ is also D, if G′ is connected,(ii)
ifG′ is disconnected with k components (blocks), say, G1,G2,…,Gk, then there must exist minimum 2-tuple dominating sets D1,D2,…,Dk of G1,G2,…,Gk such that D=D1∪D2∪⋯∪Dk and Di’s are pairwise disjoint.Proof.
(i) By Lemma5.3, we have seen that the deletion of v∉L∪D does not change the minimum 2-tuple dominating set D. Let G1 be a graph obtained after the deletion of v1∈S, so D is also the 2-tuple dominating set of G1. Again, v2∈S is being deleted from the graph G1 and the graph G2 is obtained. It also has the same 2-tuple dominating set D as of G. Proceeding in this way, we obtain the graph G′ which has same 2-tuple dominating set as G. (ii) The proof of this case follows from (ii) of Lemma 5.3.In Lemma5.3 and Corollary 5.4, the graph G′ is a subgraph of the graph G induced by V′ whose vertex set is V′ and edge set is the set of those edges of G that have both ends in V′. By keeping the statement of Corollary 5.4 in mind, we define new terms 2-tuple base graph and redundant vertex as follows.Definition 5.5 (2-tuple base graph).
Let a graphG′=(V′,E′) be induced subgraph of the graph G=(V,E), where V′⊆V, E′⊆E.The graph G′  is called the 2-tuple base graph of the graph G if the vertex set V′=L∪D and edge set E′={(i,j)∈E:i∈V′,j∈V′}, where L is the set of leading vertices corresponding to minimum 2-tuple dominating set D of G.Note 1.
IfV′=V=L∪D, then the graph G′ is the same as G and hence the graph G is the 2-tuple base graph of the graph itself.The 2-tuple base graph and its interval representation of the graph of Figure1 are given in Figures 4 and 5, respectively. Note that, in case of 2-tuple base graph, L∪D=V′, but in case of original graph, in general, L∪D≠V.Figure 4
2-tuple base graph of the graphG.Figure 5
Interval representation of the 2-tuple base graph of the graphG.Definition 5.6 (Redundant vertex).
LetG=(V,E) be a given interval graph. A vertex v∈V is said to be redundant in G, if the minimum 2-tuple dominating set D of G-v is same as ofG.An important conclusion is drawn about 2-tuple base graph as follows.Lemma 5.7.
Every interval graph has a unique 2-tuple base graph.Proof.
Suppose there exist two distinct 2-tuple base graphsG′=(V′,E′) and G′′=(V′′,E′′) of the interval graph G. Then, either (i) V′≠V′′ or (ii) E′≠E′′. Let L be the set of leading vertices corresponding to the minimum 2-tuple dominating set of G. Since G′ is the 2-tuple base graph of G, L∪D=V′ and E′={(i,j)∈E:i∈V′,j∈V′}. Again, G′′ is the 2-tuple base graph of G. Then, L∪D=V′′ and E′′={(i,j)∈E:i∈V′′,j∈V′′}. So L∪D=V′=V′′ and hence E′=E′′, which is a contradiction of our assumption. Therefore, G′ and G′′ are same.Now we define a relation between two interval graphs and it is proved that the relation is an equivalence relation.Lemma 5.8.
LetGI be the set of all interval graphs. Let a relation, denoted by  ≈, and defined by  G1≈G2⇒G1 and  G2 have same 2-tuple base graph, for all  G1,G2∈GI. Then, the relation  ≈ is an equivalence relation.Proof.
The relation is an equivalence relation since the following properties hold as well.
Reflexive
Since every graph has unique 2-tuple base graph, the same graph has the same 2-tuple base graph. Therefore,G1≈G1.Symmetric
G1≈G2⇒G2≈G1, for all G1,G2∈GI. Since, G1≈G2 means G1 and G2 have the same 2-tuple base graph, then G2 and G1 have the same 2-tuple base graph, that is, G2≈G1.Transitive
IfG1≈G2 and G2≈G3 holds for all G1,G2,G3∈GI, then G1≈G3 holds. Let us consider G1, G2 have the same 2-tuple base graph G′ and G2, G3 have the same 2-tuple base graph G′′. However we know every graph has unique 2-tuple base graph, G2 cannot have distinct 2-tuple base graph G′ and G′′. So G2 and G3 have the 2-tuple base graph G′ same as each of G1, G2. So G1 and G3 have the same 2-tuple base graph G′. So, the transitive property holds for each of GI.
Since all the properties of equivalence relation hold good inGI, then the relation ≈ defined on GI is an equivalence relation.Definition 5.9 (2-tuple equivalent).
An interval graphG1 is said to be 2-tuple equivalent to an interval graph G2 if G1≈G2,that is,G1, G2 have the same 2-tuple base graph.Definition 5.10 (2-tuple equivalent class).
LetGI be a set of interval graphs. GI is said to be 2-tuple equivalent class if any interval graph of GI is 2-tuple equivalent to each and every graph of GI.From the above notions, we have an important result about 2-tuple equivalent class.Lemma 5.11.
Equivalence relation, defined on interval graphs, makes the partition of the set of interval graphs into 2-tuple equivalent classes.Proof.
This result directly follows from the abstract algebra that every equivalence relation defined on a set makes the partition of the set into equivalent classes. Hence, the result follows. Particularly, the partitions can be found by the 2-tuple base graph. That is, we are trying to say that among all interval graphs, for each 2-tuple base graph, there is a 2-tuple equivalent class.Next, we have an another important result regarding the leading vertex corresponding to 2-tuple dominating setD.Lemma 5.12.
For an interval graphG=(V,E),
(5.5)|D|=|L|+n2,
where n2 is the number of leading vertices of order 2.Proof.
Letn1 be the number of leading vertices of order 1 and let n2 be the number of leading vertices of order 2. By definition of leading vertex, a leading vertex of order 1 corresponds to a single vertex of D and leading vertex of order 2 corresponds to two vertices of D. Since there are n1 leading vertices of order 1, then D has n1 vertices and also there are n2 leading vertices of order 2, so D has n1+2n2 vertices. Therefore, |D|=n1+2n2. Now, n1+n2=|L|. Thus, |D|=|L|+n2.


## 6. Conclusion

In this paper, we have traced out to find the minimum 2-tuple dominating set on interval graphs. The algorithm we have designed in this paper can be generalized to find minimumk-tuple dominating set and k-tuple domination number. Further investigations can be done by generalizing our Algorithm  2DIG to find k-tuple dominating set of an interval graph. We think it will reduce the next researcher’s labour.



---

*Source: 389369-2011-12-26.xml*