Ratio Mathematica Volume 46, 2023 Stability of domination in graphs Reeja Kuriakose* Parvathy K S† Abstract The stability of dominating sets in Graphs is introduced and stud- ied, in this paper. Here D is a dominating set of Graph G. In this paper the vertices of D and vertices of V − D are called donors and acceptors respectively. For a vertex u in D, let ψD(u) denote the number |N(u) ∩ (V − D)|. The donor instability or simply d- instability dDinst(e) of an edge e connecting two donor vertices v and u is |ψD(u) − ψD(v)|. The d-instability of D, ψd(D) is the sum of d-instabilities of all edges connecting vertices in D. For a vertex u not in D, let φD(u) denote the number |N(u)∩D|. The Acceptor In- stability or simply a-instability aDinst(e) of an edge e connecting two acceptor vertices u and v is |φD(u)−φD(v)|. The a-instability of D, φa(D) is the sum of a-instabilities of all edges connecting vertices in V −D. The dominating set D is d-stable if ψd(D) = 0 and a-stable if φa(D) = 0. D is stable, if ψd(D) = 0 and φa(D) = 0. Given a non negative integer α, D is α-d-stable, if dDinst(e) ≤ α for any edge e connecting two donor vertices and D is α-a-stable, if aDinst(e) ≤ α for any edge e connecting two acceptor vertices. Here we study α- stability number of graphs for non negative integer α. Keywords: Domination number; stable domination 2020 Mathematics Subject Classification: 05C69: 1 *Department of Mathematics, Govt. Polytechnic College, Koratty, Thrissur, Kerala, India; reejaiykulambil@gmail.com, reeja.kuriakose@smctsr.ac.in †Department of Mathematics, St. Mary’s College, Thrissur, Kerala, India; par- vathy.ks@smctsr.ac.in (Corresponding author). 1Received on September 15, 2022. Accepted on December 15, 2022. Published on March 20, 2023. DOI: 10.23755/rm.v46i0.1081. ISSN: 1592-7415. eISSN: 2282-8214. ©Reeja Kuriakose et al. This paper is published under the CC-BY licence agreement. 244 Reeja Kuriakose and Parvathy K S 1 Introduction Graphs considered here are the simple undirected graphs. The study of domi- nation in graphs started in 1850 with a problem of finding the minimum number of queens that are needed to place on a Chess board such that each field not occu- pied by queen can be attacked by atleast one. In 1962, Ore was the first in pub- lishing about domination in graphs. Many researchers including Ernie Cockayne, Michael Henning have contributed much to this field. A beautiful survey of results in domination is given in fundamentals of domination in graphs by W.Haynes et al. [1998]. The theory of domination has applications in the study of facility location problems, social networking and so on. Several types of domination number such as perfect domination number, connected domination number, have been defined and studied. In this paper the elements of a dominating set are called donors and the other ver- tices are called acceptors. A subset D of vertices in a social network graph with the condition that each member in D dominates almost equally many members in V − D, or that each member in V − D is dominated by almost equally many members in D, or both, plays a key role. This concept of equitable domination in graphs was defined and studied by A. Anitha, S. Arumugam and Mustapha Chel- lali. It is referred in the paper Anitha et al. [2011]. In social network problems related to marketing, banking and others the instability affects the system when adjacent acceptors are dominated by unequal number of donors or adjacent donors dominates unequal number of acceptors. This situation become worse when the instability is large. Motivated from this idea the concept of α-stability of domi- nating sets is being introduced. 2 α-d stable domination Definition 2.1. Let D be a dominating set. For a vertex u in D let ψD(u) = |N(u) ∩ (V −D)|. The donor instability or d-instability of an edge e connecting two donor vertices u and v, dDinst(e)= |ψD(u) − ψD(v)|. Let D ⊂ V , the d- instability of D, is the sum of d-instabilities of all edges connecting vertices in D, ψd(D) = ∑ e∈G[D] d D inst(e) . Definition 2.2. Let D be a dominating set. Given a non negative integer α, D is an α-d-stable dominating set, if dDinst(e) ≤ α for any edge e connecting two donor vertices. Cardinality of a minimum α-d-stable dominating set is α-d-stable domination number and it is denoted by γαd (G). Definition 2.3. A dominating set D is d-stable if ψd(D) = 0. Cardinality of a minimum d-stable dominating set is d-stable domination number and it is denoted 245 Stability of domination in graphs by γ0d(G). Observation 2.1. If α ≥ β, then γ(G) ≤ γαd (G) ≤ γ β d (G). u1 u2 u3 u4 u5 u6 u7 u8 Figure 1: Graph with γ(G) ≤ γαd (G) ≤ γ β d (G) Example 2.1. In Figure 1, D = {u1,u2} is the minimum dominating set. ψD(u1) = 4 and ψD(u2) = 2. And dDinst(u1u2) = 2. Hence D is a minimum 2-d-stable dom- inating set. And for α ≥ 2, γαd (G) = 2. If S = {u1,u7,u8}, ψD(u1) = 3 , ψD(u7) = 0 and ψD(u8) = 0. None of them are adjacent. Hence γ1d(G) = γ 0 d(G) = 3. Observation 2.2. Property of being α-d-stable dominating set is neither super- hereditary nor hereditary. Theorem 2.1. An α-d- stable dominating set D is a minimal α-d- stable domi- nating set if and only if for each vertex v in D one of the following conditions holds 1. v is an isolate of D. 2. v has a private neighbour u in V −D. 3. There exist two adjacent vertices u1 and u2 different from v in D, u1 adja- cent to v, u2 not adjacent to v and ψD(u1) = ψD(u2) + α. Proof. If an α-d- stable dominating set D is minimal, then D is an α-d- stable dominating set and for each vertex v in D, D −{v} is not an α-d- stable domi- nating set. This means that some vertex u in (V −D) ∪{v} is not dominated by D−{v} or there exist two adjacent vertices u1 and u2 different from v in D with |ψD(u1)−ψD(u2)| ≤ α but |ψD−{v}(u1)−ψD−{v}(u2)| > α. Now if some vertex u in (V − D) ∪{v} is not dominated by any vertex in D −{v}, either u = v, means v is an isolate of D or u ∈ V − D. If u is not 246 Reeja Kuriakose and Parvathy K S dominated by D−{v}, then u is adjacent only to vertex v in D. ie, v has a private neighbour u in V −D. If |ψD(u1) − ψD(u2)| ≤ α and |ψD−{v}(u1) − ψD−{v}(u2)| > α, let α = 0, then ψD(u1) = ψD(u2) and |ψD−{v}(u1) − ψD−{v}(u2)| = α + 1. Assume ψD−{v}(u1) > ψD−{v}(u2). Then u1 is adjacent to v but u2 is not adjacent to v and ψD(u1) = ψD(u2) + α. If α > 0, then assume ψD(u1) > ψD(u2). Then ψD−{v}(u1)−ψD−{v}(u2) = α+ 1. Then u1 is adjacent to v but u2 is not adjacent to v and ψD(u1) = ψD(u2) + α. Conversely, suppose that D is an α-d-stable dominating set and for each vertex v ∈ D, one of the three statements holds. We show that D is a minimal α-d-stable dominating set. If D is not a minimal α-d-stable dominating set, then there exists a vertex v ∈ D such that D−{v} is an α-d-stable dominating set. Then each vertex u in (V −D)∪{v} is adjacent with atleast one vertex in D−{v}. Then v is not an isolate of D and condition 1 does not hold. And v has no private neighbour in V − D and condition 2 does not hold. D−{v} is an α-d-stable dominating set implies for any two adjacent vertices u1 and u2 in D−{v}, ψD−{v}(u1)−ψD−{v}(u2) ≤ α. Hence condition 3 does not hold. Hence D is a minimal α-d-stable dominating set. Observation 2.3. For non negative integer α, γαd (G) = 1 ⇐⇒ γ(G) = 1. v1 v2 v3 v4 v5 v6 Figure 2: Graph with γαd (G) = 1 . Theorem 2.2. For a graph G and non negative integer α, βo(G) ≥ γαd (G). Proof. Let S be a maximum independent set. Then, every vertex in V −S is adja- cent with atleast one vertex in S. Thus S is a dominating set. S is an independent set. It follows that S is a d-stable dominating set. Hence, βo(G) ≥ γαd (G).For the graph in figure 2, γαd (G) = 2 = βo(G). Hence the bound is sharp. Theorem 2.3. If D is an α-d-stable dominating set of a graph G and u and v are adjacent vertices in D with d(v) = d(u)+k+α, k ∈ Z+, then D contains atleast k elements from (N[v]−N[u]). 247 Stability of domination in graphs Proof. If D is an α-d-stable dominating set of a graph G and u and v are adjacent vertices in D with d(v) = d(u) + k + α, k ∈ Z+, then |ψD(v)−ψD(u)| ≤ α. Hence |N[v] ∩ (V − D)| ≤ |N[u] ∩ (V − D)| + α. Thus, d(v) − d(u) ≤ |(N[v]−N[u])∩D|+ α. Hence D contains atleast k elements from (N[v]−N[u]). Corolary 2.1. If D is a d-stable dominating set of a graph G and u and v are adjacent vertices in D with d(v) > d(u), then D contains atleast d(v) − d(u) elements from (N[v]−N[u]). Corolary 2.2. If u is a pendant vertex adjacent to v, D is a d-stable dominating set and u,v ∈ D, then N[v] ⊂ D. Theorem 2.4. For any non negative integer β, there exist graph G with γ0d(G) > γ1d(G) > γ 2 d(G)...... > γ β d (G) Proof. Take k = β + 1 Construct G as follows, Step 1:- Let H be the complete graph with vertex set {a1,a2, ....,ak}. Step 2:- Let Ai = {ai,1,ai,2, ...,ai,i+1} for i = 1,2, ...,k. Form G by joining each vertices in Ai with ai in H for i = 1,2...,k. Let D be a d-stable dominating set, Bi = {ai,ai,1,ai,2, ...,ai,i+1} and Ci = Bi∩D. If ar,as ∈ D with r < s then by corollary 2.1, D contains s−r elements from As and hence by corollary 2.2, N[as] ⊂ D. Thus Bs ⊂ D. Thus Ci = Bi for all i = 1,2, ...,k. Hence D = V (G) or D = A1∪A2∪A3∪......∪As−1∪As+1∪.....∪Ak−1∪Ak∪ {as}. Hence we take D = A1∪A2∪A3∪......∪As−1∪As+1∪.....∪Ak−1∪Ak∪{as}. Thus |Ci| = i + 1 for i 6= s and |Cs| = 1. Then, |D| = 2 + 3 + ..... + (s) + 1 + (s + 2) + .... + (k + 1) = (k+1)(k+2) 2 − (s + 1). Hence |D| is minimum when (k+2)(k+1) 2 −(s+1) is minimum. That is when s = k. And D = A1 ∪ A2 ∪ A3 ∪ ...... ∪ Ak−1 ∪{ak} will form a d- stable dominating set with |D| = (k+2)(k+1) 2 − (k + 1). Hence γ0d(G) = (k+2)(k+1) 2 − (k + 1) = (k)(k+1) 2 . Similarly, γ0d(G) = (k)(k+1) 2 γ1d(G) = k(k−1) 2 + 1 ... γ β d (G) = (k−β+1)(k−β) 2 + β. Figure 3 illustrates the graph with γ0d(G) > γ 1 d(G) > γ 2 d(G). 248 Reeja Kuriakose and Parvathy K S a1 a2 a3 a1,1 a1,2 a2,2 a2,3 a2,2 a3,1 a3,2 a3,4 a3,3 Figure 3: Graph with γ0d(G) > γ 1 d(G) > γ 2 d(G) 3 α-a-stable domination Definition 3.1. Let D be a dominating set. For a vertex u not in D, let φD(u) = |N(u) ∩ D|. The Acceptor Instability or a-instability of an edge e connecting two acceptor vertices u and v is, aDinst(e) = |φD(u)−φD(v)|. The a-instability of D, φa(D) is the sum of a-instabilities of all edges connecting vertices in V −D, φa(D) = ∑ e∈G[V−D] a D inst(e). Definition 3.2. Let D be a dominating set. Given a non negative integer α, D is an α-a-stable dominating set, if aDinst(e) ≤ α for any edge e connecting two acceptor vertices. Cardinality of a minimum α-a-stable dominating set is α-a- stable domination number and denoted by γαa (G). Definition 3.3. The dominating set D is a-stable if φa(D) = 0 . Minimum cardi- nality of an a-stable dominating set is a-stable domination number and denoted by γ0a(G). Observation 3.1. If α ≥ β, then γ(G) ≤ γαa (G) ≤ γβa (G) Example 3.1. In Figure 1, D = {u1,u2} is the minimum dominating set. φD(u3) = φD(u4) = φD(u5) = φD(u6) = φD(u7) = φD(u8) = 1. Hence D is a minimum a-stable dominating set and γαa (G) = 2 for all non negative integer α. 249 Stability of domination in graphs Observation 3.2. Property of being α-a-stable dominating set is neither super- hereditary nor hereditary. Theorem 3.1. An α-a- stable dominating set D is a minimal α-a- stable domi- nating set if and only if for each vertex v in D one of the following conditions holds 1. v is an isolate of D. 2. v has a private neighbour u in V −D. 3. There exist two adjacent vertices u1 and u2 in V-D, u1 adjacent to v, u2 not adjacent to v and φD(u2) = φD(u1) + α. Proof. If an α-a- stable dominating set D is minimal then D is an α-a- sta- ble dominating set and for each vertex v in D, D − {v} is not an α-a- stable dominating set. This means that some vertex u in (V − D) ∪{v} is not domi- nated by D −{v} or there exist two adjacent vertices u1 and u2 in V − D with |φD(u1)−φD(u2)| ≤ α but |φD−{v}(u1)−φD−{v}(u2)| > α. Now if some vertex u in (V −D)∪{v} is not dominated by any vertex in D−{v}, either u = v, means v is an isolate of D or u ∈ V −D. If u is not dominated by D −{v}, then u is adjacent only to vertex v in D. ie, v has a private neighbour u in V −D. If |φD(u1) − φD(u2)| ≤ α and |φD−{v}(u1) − φD−{v}(u2)| > α, let α = 0, then φD(u1) = φD(u2) and |φD−{v}(u1) − φD−{v}(u2)| = α + 1. Assume φD−{v}(u2) > φD−{v}(u1). Then u1 is adjacent to v but u2 is not adjacent to v and φD(u2) = φD(u1) + α. If α > 0, then assume φD(u2) > φD(u1). Then φD(u2)−φD(u1) = α and φD−{v}(u2)−φD−{v}(u1) = α+1. Then u1 is adjacent to v but u2 is not adjacent to v and φD(u2) = φD(u1) + α. Conversely, suppose that D is an α-a-stable dominating set and for each vertex v ∈ D, one of the three statements holds. We show that D is a minimal α-a- stable dominating set. If D is not a minimal α-a-stable dominating set,then there exists a vertex v ∈ D such that D −{v} is an α-a-stable dominating set. Then each vertex u in (V − D) ∪{v} is adjacent with atleast one vertex in D −{v}. Then v is not an isolate of D and condition 1 does not hold. And v has no pri- vate neighbour in V − D and condition 2 does not hold. If D −{v} is an α-a- stable dominating set then for any adjacent vertices u1 and u2 in (V −D) ∪{v}, φD−{v}(u2) − φD−{v}(u1) ≤ α. Hence condition 3 does not hold. Hence D is a minimal α-a-stable dominating set. Observation 3.3. For non negative integer α, γαa (G) = 1 ⇐⇒ γ(G) = 1 Theorem 3.2. For α ≥ 1, γαa (G) = 2 ⇐⇒ γ(G) = 2 250 Reeja Kuriakose and Parvathy K S Proof. If γ(G) = 2, then for a minimum dominating set D, |D| = 2 |D| = 2 ⇒ φD(v) = 1 or φD(v) = 2 ∀v ∈ V −D ⇒ |φD(v1)−φD(v2)| ≤ 1, ∀v1,v2 ∈ V −D ⇒ γαa (G) = 2 Conversely, if γαa (G) = 2, then γ(G) 6= 1. If D is a minimum α-a- stable domi- nating set , then |D| = 2, and D is a dominating set. Thus, γ(G) = 2 Theorem 3.3. For any graph G and non negative integer α, γαa (G) ≤ γp(G). And this bound is sharp. Proof. If D is a γP - set, then |N[v]∩D| = 1, ∀v ∈ (V −D). Hence φD(v) = 1, for all v ∈ (V − D). And so D is an a-stable dominating set . Thus every perfect dominating set is an a-stable dominating set . Hence, γαa (G) ≤ γp(G). For G = P3n, γp(G) = n = γαa (G). So we can see that the bound is sharp. a1 a2 a3 b′1,1 b1,1 b1,1” b2,2” b2,2 b2,1” b2,1 b′2,2 b′2,1 b′3,1 b′3,3 b′3,2 b3,1” b3,1 b3,2 b3,2” b3,3 b3,3” Figure 4: Graph with γ0a(G) > γ 1 a(G) > γ 2 a(G) 251 Stability of domination in graphs Theorem 3.4. For any positive integer β, there exist graph G with γ0a(G) > γ1a(G) > γ 2 a(G)...... > γ β a (G). Proof. Let k = β + 1. Construct G as follows Step 1:Let H be the complete graph with vertex set {a1,a2, ...,ak} Step 2: For each i take i copies of P3 with vertex set {bi,j,b′i,j,bi,j”} for j = 1,2, ..., i and join b′i,j with ai for each j = 1,2, ...., i. Let Aji = {bij,b ′ ij,bij”} for j = 1,2, ...i and Ai = {ai}∪∪ij=1{bij,b′ij,bij”} for all i ∈{1,2, ...,k}. Let D be an a-stable dominating set. If ai ∈ D then |Ai ∩D| ≥ i + 1. Let r be the smallest integer such that ar /∈ D. Then |Ar ∩D| ≥ r. If s > r and as /∈ D, since γainst(ar,as) = 0, b′sj ∈ D for atmost r values of j. And if there exist j for which b′sj /∈ D then bsj,bsj” ∈ D. =⇒ |As ∩D| ≥ r + 2(s− r) = 2s− r ≥ s + 1 Hence, |D| ≥ |A1 ∩D|+ |A2 ∩D|+ |A3 ∩D|+ ... + |Ar−1 ∩D|+ |Ar ∩D|+ |Ar+1 ∩D|+ ... + |Ak ∩D| ≥ 2 + 3 + ... + (r −1 + 1) + r + (r + 2) + .... + (k + 1) = 1 + 2 + ... + k + k −1 = k(k+1) 2 + (k −1) . Thus, γ0d(G) ≥ k(k+1) 2 + (k −1). And D′ = {a1, ....,ak−1}∪∪ki=1{b′i1,b′i2, ...b′ii} is an a-stable dominating set with |D′| = k(k+1) 2 + (k −1). Hence, γ0a(G) ≤ k(k+1) 2 + (k −1) Thus, γ0a(G) = k(k+1) 2 + (k −1) Similarly, γ1a(G) = k(k+1) 2 + (k −2) γ2a(G) = k(k+1) 2 + (k −3) γ3a(G) = k(k+1) 2 + (k −4) ... γβ−1a (G) = k(k+1) 2 + 1 γβa (G) = k(k+1) 2 Figure 4 illustrates the graph with γ0a(G) > γ 1 a(G) > γ 2 a(G). 4 α-stable domination Definition 4.1. A dominating set D is stable, if ψd(D) = 0 and φa(D) = 0. Min- imum cardinality of a stable dominating set is called stable domination number and denoted by γ0(G). 252 Reeja Kuriakose and Parvathy K S Definition 4.2. If a dominating set D is an α-d-stable dominating set and α-a - stable dominating set, then D is called an α-stable dominating set and cardinality of a minimum α-stable dominating set is defined as α-stable domination number and denoted by γα(G) Observation 4.1. If a minimum α -a-stable dominating set is an α-d-stable dom- inating set, then γα(G) = γαa (G). And if a minimum α-d- stable dominating set is an α-a- stable dominating set, then γα(G) = γαd (G). Observation 4.2. If α ≥ β, then γ(G) ≤ γα(G) ≤ γβ(G). Definition 4.3. Minimum α so that γα(G) = γ(G) is called stable dominating index and denoted by Isd(G). Example 4.1. In figure 1, the minimum d-stable dominating set {u1,u7,u8} is an a-stable dominating set. Hence {u1,u7,u8} is a minimum stable dominating set and γ0(G) = 3. A minimum 1-d-stable dominating set {u1,u7,u8} form a 1-a- stable dominating set and hence {u1,u7,u8} is a minimum 1-stable dominating set and γ1(G) = 3. And minimum dominating set {u1,u2} is a 2-a- stable dominating set and a 2-d- stable dominating set. {u1,u2} form a minimum 2-stable dominating set. Hence, γ2(G) = 2. And ∀α ≥ 2, γα(G) = 2 = γ(G). Hence, Isd(G) = 2. Compliment of a minimum α-stable dominating set need not be an α-stable dominating set. In graph figure 1, {u1,u2,u3} is a minimum 1-stable dominating set but its compliment is not a 1-stable dominating set. Observation 4.3. Property of being α-stable dominating set is neither super- hereditary nor hereditary. Theorem 4.1. For any graph G and for any non-negative integer α, γ(G) = 1 ⇐⇒ γα(G) = 1. Proof. If γ(G) = 1, then the single vertex set {v} which dominates all vertices of G, is an α-d-stable dominating set and an α-a-stable dominating set. Then γα(G) = 1. Also any α-stable dominating set is a dominating set. So, if γα(G) = 1 then γ(G) = 1. Lemma 4.1. For any graph G and for any non negative integer α, γα(G) = n ⇐⇒ G = Kn. Proof. If G 6= Kn, there is atleast one vertex v with d(v) ≥ 1. Then V −{v} is an α-stable dominating set. This means that γα(G) ≤ n − 1. Hence if γα(G) = n, then G = Kn. If G = Kn, then γα(G) = n trivially. 253 Stability of domination in graphs Theorem 4.2. For a graph G with δ(G) ≥ 1, γα(G) ≤ n−1. Proof. From lemma 3.9 it is clear that γα(G) ≤ n−1. Theorem 4.3. For any non negative integer α, γα(G) = γ(G) for the following Graphs • Complete graph Kn • Path Pn • Cycle Cn • Wheel graph Wn • Helm graph Hn Proof. In these graphs minimum dominating set D, form an α-stable dominating set. Hence α-stable domination number is same as its domination number. Theorem 4.4. Let G and H be two graphs of order n1 and n2 , then for any non-negative integer α , • γαa (G2H) ≤ min{n1γαa (H),n2γαa (G)} • γαd (G�H) ≤ min{n1γ α d (H),n2γ α d (G)} • γα(G�H) ≤ min{n1γα(H),n2γα(G)}. Proof. Let SH be a minimum α-a-stable dominating set of H. Let us see that S = V (G) ×SH is an α-a-stable dominating set of G�H . If (u,v) ∈ (V (G) × V (H)) −S. Then (u,v) is adjacent to atleast one vertex in S. And if (u1,v1) ∈ (V (G)×V (H))−S and (u2,v2) ∈ (V (G)×V (H))−S and (u1,v1) adjacent to (u2,v2). Then, φS(u1,v1) = |{(u,v) ∈ S : (u1,v1) adjacent to (u,v)}| = |{(u,v) ∈ S : u1 = u and v1 adjacent to v}∪ {(u,v) ∈ S : u1 adjacent to u and v1 = v}| = |{(u,v) ∈ S : u1 = uand v1 adjacent tov}| = φSH (v1). φS(u2,v2) = φSH (v2). And |φS(u1,v1)−φS(u2,v2)| = |φSH (v1)−φSH (v2) ≤ α. Hence S is an α- a-stable dominating set of G�H. 254 Reeja Kuriakose and Parvathy K S Similarly, if SG is a minimum α-a-stable dominating set of G, then SG × V (H) is an α-a-stable dominating set of G�H. Thus, γαa (G2H) ≤ min{n1γαa (H),n2γαa (G)}. Let SH be a minimum α-d-stable dominating set of H. Let S = V (G) ×SH. If (u,v) ∈ (V (G)×V (H))−S, then (u,v) is adjacent to atleast one vertex in S. And if (u1,v1) ∈ S and (u2,v2) ∈ S and (u1,v1) adjacent to (u2,v2). Then, ψS(u1,v1) = |{(u,v) ∈ (V (G)×V (H))−S : (u1,v1) adjacent to (u,v)}| = |{(u,v) ∈ (V (G)×V (H))−S : u1 = u and v1 adjacent to v}∪ {(u,v) ∈ (V (G)×V (H))−S : u1 adjacent to u and v1 = v}| = |{(u,v) ∈ (V (G)×V (H))−S : u1 = u and v1 adjacent to v}| = ψSH (v1). Similarly ψS(u2,v2) = ψSH (v2). Thus |ψS(u1,v1)−ψS(u2,v2)| = |ψSH (v1)−ψSH (v2) ≤ α Thus S is an α-d-stable dominating set of G2H. Similarly, if SG is a minimum α-d-stable dominating set of G, SG ×V (H) is an α-d-stable dominating set of G2H. Thus, γαd (G2H) ≤ min{n1γ α d (H),n2γ α d (G)}. Hence, γα(G2H) ≤ min{n1γα(H),n2γα(G)}. Remark 4.1. The bound in theorem 3.12 is attained if G = Kn and H = K2; because γα(Kn2K2) = 2 = min{2γα(Kn),nγα(K2)}. Theorem 4.5. For any two graphs G and K and non negative integer α, α-stable domination number of its corona, γα(GoK) = |V (G)|. Proof. Let {v1,v2, .....,vn} be the vertices of G and {u1,u2, ....um} be the ver- tices of K. Ki be the ith copy K in GoK. To make sure that each vertex of Ki is dominated, we need atleast one vertex of Ki or vi. Thus the dominat- ing set contains atleast n vertices. Let D = {v1,v2, .......,vn}. Then each ver- tex of V − D is adjacent with exactly one vertex of D and each vertex of D dominates exactly m vertices in V − D. And so ψD(v) = m, ∀v ∈ D and φD(v) = 1, ∀v ∈ V − D. Therefore, |φD(v1) − φD(v2)| = 0,∀v1,v2 ∈ V − D and |ψD(v1) − ψD(v2)| = 0,∀v1,v2 ∈ D. And so D is a minimum α-stable dominating set. Thus γα(GoK) = n = |V (G)|. 255 Stability of domination in graphs 5 Conclusions Motivated from this idea the concept of α-stability of dominating sets is being introduced. The stability of dominating sets in Graphs is introduced and studied, in this paper. In social network problems related to marketing, banking and oth- ers the instability affects the system when adjacent acceptors are dominated by unequal number of donors or adjacent donors dominates unequal number of ac- ceptors. Several types of domination number have been defined and studied. This situation become worse when the instability is large. Here we study α- stability number of graphs for non negative integer α. Instability of domination in Graphs the concept of stability of domination in Graphs are defined. The open problems are Characterize the graphs with Isd(G) = 0. Characterize the graphs for which the compliment of minimum α-stable dominating set is an α-stable dominating set. Develop an algorithm to find the α-stable domination number of a graph. In future we extended this topic. References A. Anitha, S. Arumugam, and M. Chellali. Equitable domination in graphs. Dis- crete Mathematics, Algorithms and Applications, 3:311–321, 2011. T. W.Haynes, S. T.Hedetniemi, and P. J.Slater. Fundamentals of Domination in Graphs. Marcel Dekker, New York, 1998. 256