Ratio Mathematica                                                                           Volume 45, 2023 
 

 

 

Changing and Unchanging strong efficient 

edge domination number of some standard 

graphs when a vertex is removed or an edge is 

added 
 

 

M. Annapoopathi1 

N. Meena2 
 

 
 

Abstract 

Let 𝐺 = (𝑉, 𝐸) be a simple graph. A subset S of E(G) is a strong (weak) efficient edge 
dominating set of G if │Ns[e]  S│ = 1 for all e  E(G)(│Nw[e]  S│ = 1 for all e  

E(G)) where Ns(e) ={f / f  E(G), f is adjacent to e & deg f ≥ deg e}(Nw(e) ={f / f  

E(G), f is adjacent to e & deg f ≤ deg e}) and Ns[e]=Ns(e) {e}(Nw[e] = Nw(e) {e}). 

The minimum cardinality of a strong efficient edge dominating set of G (weak efficient 

edge dominating set of G) is called a strong efficient edge domination number of G and 

is denoted by 𝛾′
𝑠𝑒

(𝐺) (𝛾′
𝑤𝑒

(𝐺)).When a vertex is removed or an edge is added to the 

graph, the strong efficient edge domination number may or may not be changed. In this 

paper the change or unchanged of the strong efficient edge domination number of some 

standard graphs are determined, when a vertex is removed or an edge is added. 

 

Keywords: Domination, edge domination, strong edge domination, efficient edge 

domination, strong efficient edge domination. 

 

AMS subject classification: 05C693 
 

 
1 Reg.No:17231072092002, Research Scholar, Department of Mathematics, P.G. & Research Department 
of Mathematics, The M.D.T. Hindu College, Tirunelveli. (Affiliated to Manonmaniam Sundaranar 

University, Tirunelveli – 627 012, Tamil Nadu, India) and Assistant Professor, National Engineering 

College, Kovilpatti - 628503, Tamil Nadu, India. Email: annapoopathi.nec@gmail.com 
2  Assistant Professor, P.G. & Research Department of Mathematics, the M.D.T. Hindu College, 

Tirunelveli. (Affiliated to Manonmaniam Sundaranar University, Tirunelveli – 627 012, Tamil Nadu, 

India). Email: meena@mdthinducollege.org 
3  Received on July 10, 2022. Accepted on October 15, 2022. Published on January 30, 2023. doi: 

10.23755/rm.v45i0.1024. ISSN: 1592-7415. eISSN: 2282-8214. ©The Authors. This paper is published 

under the CC-BY license agreement. 

257

mailto:annapoopathi.nec@gmail.com
mailto:meena@mdthinducollege.org


M. Annapoopathi and N. Meena 
 

 

1. Introduction 

It is meant by the graph that it is a finite, undirected graph without loops and multiple 

edges. The concept of domination in graphs was introduced by Ore. Two volumes on 

domination have been published by T. W. Haynes, S. T. Hedetniemi and P. J. Slater [4, 

5]. Let G be a graph with vertex set V and edge set E. A subset D of V (G) is called a 

strong dominating set of G if every vertex in V- D is strongly dominated by at least one 

vertex in D. Similarly, a set D is a subset of V (G) is called a weak dominating set of G 

if every vertex in V- D is weakly dominated by at least one vertex in D. The strong 

(weak) domination number 𝛾𝑠(𝐺) (𝛾𝑤 (𝐺)) respectively of G is the minimum cardinality 
of a strong (weak) dominating set of G. A subset D of V (G) is called an efficient 

dominating set of G if for every vertex u ∈  V (G), |𝑁[𝑢] ∩ 𝐷| = 1  [1, 2]. Edge 
dominating sets were also studied by Mitchell and Hedetniemi [6, 7].  A subset F of 

edges in a graph G = (V, E) is called an edge dominating set of G if every edge in E-F is 

adjacent to at least one edge in F. The edge domination number 𝛾′(𝐺) of a graph G is 
the smallest cardinality among all minimum edge dominating sets of G. The degree of 

an edge uv is defined to be deg u + deg v - 2. An edge uv is called an isolated edge if 

deg uv = 0. A subset F of E is called an efficient edge dominating set if every edge in E 

is either in F or dominated by exactly one edge in F. The cardinality of minimum 

efficient edge dominating set is called the edge domination number of G. Motivated by 

these definitions; strong efficient edge domination in graphs is defined as follows. A 

subset S of E(G) is a strong (weak) efficient edge dominating set of G if |𝑁𝑠[𝑒] ∩ 𝑆| =
1  for all 𝑒 ∈ 𝐸(𝐺) [ |𝑁𝑤 [𝑒] ∩ 𝑆| = 1  for all 𝑒 ∈ 𝐸(𝐺)]  where 𝑁𝑠 (𝑒) = { 𝑓/𝑓 ∈
𝐸(𝐺) & 𝑑𝑒𝑔 𝑓 ≥ deg 𝑒} ( 𝑁𝑤 (𝑒) = {𝑓/𝑓 ∈ 𝐸(𝐺) & 𝑑𝑒𝑔 𝑓 ≤ deg 𝑒} ) and 𝑁𝑠[𝑒] =
 𝑁𝑠(𝑒) ∪ {𝑒}  (𝑁𝑤 [𝑒] =  𝑁𝑤 (𝑒) ∪ {𝑒}) .The minimum cardinality of a strong efficient 
edge dominating set of G (weak efficient edge dominating set of G) is called as a strong 

efficient edge domination number of G (weak efficient edge domination number of G ) 

and also  denoted by 𝛾′𝑠𝑒 (𝐺) (𝛾
′
𝑤𝑒

(𝐺)). 

 

Definition 1.1. Let 𝐺 = (𝑉, 𝐸)  be a simple graph. Let 𝐸(𝐺) =
{𝑒1, 𝑒2, 𝑒3, 𝑒4, … … … … . 𝑒𝑛 }. An edge 𝑒𝑖 is said to be the full degree edge if and only if 
deg 𝑒𝑖 = n-1. 
 

Observation 1.2.  𝛾 ′
𝑠𝑒

(𝐺) = 1 if and only if G has a full degree edge. 

 

Observation 1.3. 𝛾 ′
𝑠𝑒

(𝐾1,𝑛) = 1, 𝑛 ≥ 1   and  𝛾
′
𝑠𝑒

(𝐷𝑟,𝑠) = 1, 𝑟, 𝑠 ≥ 1  

 

Theorem 1.4. For any path 𝑃𝑚 ,    𝛾
′
𝑠𝑒

( 𝑃𝑚 )  = {

 𝑛,                𝑖𝑓 𝑚 = 3𝑛 + 1, 𝑛 ≥ 1
𝑛 + 1,                𝑖𝑓 𝑚 = 3𝑛, 𝑛 ≥ 2

𝑛 + 1,           𝑖𝑓 𝑚 = 3𝑛 + 2, 𝑛 ≥ 1
 

 

Theorem 1.5. NnnC
nse

= ,)(
3

'


 

258



Changing and Unchanging strong efficient edge domination number of some standard 

graphs when a vertex is removed or an edge is added 

 

Theorem 1.6. Let Wm be a wheel graph. Then Wm has a strong efficient edge 

dominating set if and only if m = 3n, n ≥ 2 and  𝛾′
𝑠𝑒

(𝑊3𝑛) = 𝑛, n ≥ 2. 

 

2. Main Results 

Definition 2.1. )})(())(/()({)()(
''0'

GeGGEeGE
sesese

 =+=  

)})(())((/)({)()(
'''

GeGGEeGE
sesese

 +=
+

, 

)})(())((/)({)()(
'''

GeGGEeGE
sesese

 +=
−

 
 

Example 2.2. Consider the following graph 

 

 

 

 

 

 

 

 

Since e5 is the full degree edge of G, )(
'

G
se

 =1.  {e3, e6} is the unique strong efficient 

edge dominating set of G – e5. Therefore ))((2))((
'

5

'
GeG

sese
 =−  and e5 is the full 

degree edge of G – e3 and )(1)(
'

3

'
GeG

sese
 ==− . Hence ))(()(

3

''
eGG

sese
−=  . 

 

Definition 2.3. )}()(/)({)()(
''0'

GvGGVvGV
sesese

 =−=  

)}()(/)({)()(
'''

GvGGVvGV
sesese

 −=
+

, 

)}()(/)({)()(
'''

GvGGVvGV
sesese

 −=
+

 
 

Example 2.4. Consider the following graph 

 

 

 

 

 

 

 

 

 

S= {e4, e7} is the strong efficient edge dominating set of G and )(
'

G
se

 =2. 

3,1,)()(
''

==− iGvG
seise

  and 3,1,)()(
''

− iGvG
seise

  

 

e2

2 

e1

2 

e3

2 

e5

2 

e4

2 

e6

2 

e1 e4 

e2 
e3 e6 

e5 

e7 

v1 

v2 v3 v4 

v5 
v6 

259



M. Annapoopathi and N. Meena 
 

Theorem 2.5. Let G = P3n, .1n  Then =
+

)()(
'

GV
se

 

Proof: Case (1): Let G = P3n, .1n  Let v be the end vertex of G. Then G – v = P3n-1. 

nnPP
nsense

=+−==
+−−

11)()(
2)1(3

'

13

'
  and 1)(

'
+= nG

se
 . Therefore

)()(
''

GvG
sese

 − . Hence )()(
'

GVv
sei

+
 . 

Case (2): Let 11,
3

−= nkvv
k

. Thus G – v = P3k --1 ∪ P3n-3k and kP kse =− )( 13
'

 ,

1)()(
)(3

'

33

'
+−==

−−
knPP

knseknse
 . Therefore )()()(

33

'

13

''

knseksese
PPvG

−−
+=−   = 

)(11
'

Gnknk
se

=+=+−+ . Hence )()(
0'

GVv
se

 . 

Case (3): Let 11,
13

−=
+

nkvv
k

. Thus G – v = P3k ∪P3n-3k-1 and 1)( 3
'

+= kP
kse

 , 

knPP
knseknse

−==
+−−−−

)()(
2)1(3

'

133

'
 . Therefore )()()(

133

'

3

''

−−
+=−

knseksese
PPvG  = 

)(11
'

Gnknk
se

=+=−++ . Hence )()(
0'

GVv
se

 . 

Case (4): Let 21,
23

−=
+

nkvv
k

. Thus G – v = P3k+1 ∪P3n-3k-2 and kP kse =+ )( 13
'

 , 

1)()(
1)1(3

'

233

'
−−==

+−−−−
knPP

knseknse
 . Therefore 

)()()(
233

'

13

''

−−+
+=−

knseksese
PPvG    

11 −=−−+= nknk  )(
'

G
se

 . Hence )()(
'

GVv
se

−
 . 

Case (5): when v = v2 or v3n-1. Thus G-v = P3n-2 ∪ P1 having no strong efficient 

dominating set. From the above given the cases it is identified that, =
+

)()(
'

GV
se  

 

Theorem 2.6. Let G = P3n+1, .1n  Then =
−

)()(
'

GV
se

 

Proof: Case (1): Let G = P3n+1, .1n  Let v be the end vertex of G. Then G – v = P3n. 

1)(
'

+=− nvG
se

  but nG
se

=)(
'

 . Therefore )()(
''

GvG
sese

 − . Hence )()(
'

GVv
se

+
  

Case (2): Let 11,
3

−= nkvv
k

. Thus G – v = P3k --1 ∪ P3n+1-3k. Therefore 

)()()(
313

'

13

''

knseksese
PPvG

−+−
+=−   = )()(

1)(3

'

2)1(3

'

+−+−
+

knsekse
PP  =

)(
'

Gnknk
se

==−+ . Hence )()(
0'

GVv
se

 . 

Case (3): Let 11,13 −= + nkvv k . Thus G – v = P3k ∪ P3n-3k. Therefore 

)()()(
)(3

'

3

''

knseksese
PPvG

−
+=−   = )(211

'
Gnnknk

se
=+=+−++ . Hence 

)()(
'

GVv
se

+
 . 

Case (4): Let 21,23 −= + nkvv k . Thus G – v = P3k+1 ∪P3n-3k-1 = P3k+1 ∪P3(n-k-1)+2  and, 

Therefore )()()(
2)1(3

'

13

''

+−−+
+=−

knseksese
PPvG  nknk =+−−+= 11  )(

'
G

se
= . 

Hence )()(
0'

GVv
se

 . 

Case (5): when v = v2 or v3n. G-v = P3n-1 ∪P1 which has no strong efficient dominating 

set. From the above all the cases, =
−

)()(
'

GV
se  

 

Theorem 2.7. Let G = P3n+2, .1n  Then =
−

)()(
'

GV
se

 

260



Changing and Unchanging strong efficient edge domination number of some standard 

graphs when a vertex is removed or an edge is added 

Proof: Case (1): Let G = P3n+2, .1n  Let v be the end vertex of G. Then G – v = P3n+1. 

nPvG
nsese

==−
+

)()(
13

''
  but 1)(

'
+= nG

se
 . Therefore )()(

''
GvG

sese
 − . Hence 

)()(
'

GVv
se

−
  

Case (2): Let 11,
3

−= nkvv
k

. Thus G – v = P3k --1 ∪ P3n+2-3k. Therefore 

)()()(
323

'

13

''

knseksese
PPvG

−+−
+=−   = )()(

2)(3

'

2)1(3

'

+−+−
+

knsekse
PP  =

)(11
'

Gnknk
se

=+=+−+ . Hence )()(
0'

GVv
se

 . 

Case (3): Let 11,
13

−=
+

nkvv
k

. Thus G – v = P3k ∪ P3n-3k+1. Therefore 

)()()(
1)(3

'

3

''

+−
+=−

knseksese
PPvG   = )(11

'
Gnknk

se
=+=−++ . Hence 

)()(
0'

GVv
se

 . 

Case (4): Let 21,
23

−=
+

nkvv
k

. Thus G – v = P3k+2 ∪P3n-3k-1 = P3k+2 ∪P3(n-k-1)+2  

and, Therefore )()()(
2)1(3

'

23

''

+−−+
+=−

knseksese
PPvG  112 +=−−++= nknk  

)(
'

G
se

= . Hence  )()(
0'

GVv
se

 . 

Case (5): when v = v2 or v3n+1. G-v = P3n-2 ∪P1 which has no strong efficient dominating 

set. From the above all the cases, =
−

)()(
'

GV
se

 

 

Theorem 2.8. Let 1,
3

= nCG
n

. Then ).()()(
0'

GVGV
se

=
 

Proof:  

Let 1,
3

= nCG
n .  Let )(GVv  . Then )(

'
G

se
 =n, G – v = P3n-1 and 

)()(
2)1(3

'

13

'

+−−
=

nsense
PP  n= Therefore )()(

''
GvG

sese
 =− . Hence ).()()(

0'
GVGV

se
=  

 

Theorem 2.9. Let 2,
,1

= nKG
n

. Then ).()()(
0'

GVGV
se

=
 

Proof:  

Let 2,
,1

= nKG
n

.  Let )(GVv  . Then )(
'

G
se

 =1, G – v = K1, n-1 and 1)( 1,1
'

=
−nse

K .  

Therefore )()(
''

GvG
sese

 =− . Hence ).()()(
0'

GVGV
se

=  

 

Theorem 2.10. Let 1,,
,

= srDG
sr

. Then .2|)()(|
0'

−+= srGV
se  

Proof:  

Let 1,,
,

= srDG
sr

.  Let V (G) = }1,1/,,,{ sjrivuvu
ji

 , 

 .1,1/,,)( sjrivvuuuvGE
ji

= Let v = ui or vj. Then )(
'

G
se

 =1, G – v = Dr -1, s = 

Dr, s-1 and 1)()( 1,
'

,1

'
==

−− srsesrse
DD  . Therefore )()(

''
GvG

sese
 =− . Hence 

 .,)()()( 0' vuGVGV
se

−=
Therefore 

( ) 2|)(| 0' −+= srGV
se

 

 

Theorem 2.11. Let 2,3 = nWG n . Then )()(
0'

GVv
se

  if )(
1

Kv   and )()(
'

GVv
se

−
  

if 
 

( )
13 −


n

CVv
 

261



M. Annapoopathi and N. Meena 
 

Proof:  

Let 2,
3

= nWG
n

. Let V(G) = }31/,{ nivv
i

 , 

 131,31/,,)(
131

−=
+

ninjvvvvvvGE
niij  

Case (1): G – v = C3n. Therefore nCvG nsese ==− )()( 3
''

 . Hence )()(
0'

GVv
se

 . 

Case (2): Let v = vi, ni 31  . G – v = F3n-1. Therefore 

nFFvG
nsensese

===−
+−−

)()()(
2)1(3

'

13

''
 . but nG

se
2)(

'
= . Hence )()(

''
GvG

sese
 − . 

Therefore )()(
'

GVv
se

−
  

 

Theorem 2.12. 

 
Let G = P3n, .2n  Let e = uv be any edge incident with any vertex of G and G’ = G+e. 

Then 1)()(
''

−=+ GeG
sese


 
if e is incident with u1 or 231,3 − niu i  and )(

'
eG

se
+  

has no strong efficient edge dominating set if e is incident with u2, u3n-1, 

231,
23

−
+

niu
i  

Proof:
  

Let G = P3n, .2n  V(G) = }31/{ niui  ,  131/)( 1 −== + niuueGE iii . Let e = 
uv be the new edge incident with any vertex of G and G’ = G+e. 

Case 1: Let e be an end edge of G’. Then G’ = P3n+1. Therefore nPG nsese == + )()'( 13
''


 

but .1)(
'

+= nG
se

 Therefore ).()(
''

GeG
sese

 +  Hence ).()(
'

GEe
se

−


 
Case 2:  Let the edge e be incident with the vertex u2. Let S be a strong efficient edge 

dominating set of G’. Suppose .2n  Among all the edges, the edge e2 have maximum 

degree. It must belong to S. It strongly efficiently dominates e, e3, e1. Also the edges e5, 

e8, e11,  …, e3n-4  belong to S. If the edge e3n-2 belongs to S, then |𝑁𝑆[𝑒3𝑛−3] ∩ 𝑆| =
|{𝑒3𝑛−4, 𝑒3𝑛−2}| = 2 > 1 , a contradiction. Hence G’ has no strong efficient edge 
dominating set. The proof is similar if the edge e is added at the vertex u3n-1. 

Case 3:  Let the edge e be incident with the vertex u3. e2 and e3 are the only maximum 

degree edges. Hence any strong efficient edge dominating set contains either e2 or e3 

.Then S1 = {e1, e3, e6,  …., e3n-3, e3n-1} , S2 = {e2, e4, e7, …. e3n-2} are the strong efficient 

edge dominating sets of G’. Therefore |S1|=n+1, |S2|=n. Hence )()'(
''

GnG
sese

 = . 

Therefore ).()(
'

GEe
se

−
  The proof is similar if the edge e is incident with the vertex 

12,
3

− niu
i  

Case 4:  Let the edge e be incident with the vertex u4. Then S = {e2, e4, e7, …. e3n-2} is 

the unique strong efficient edge dominating set of G’ and nG
se

=)'(
'

 . Therefore 

).()(
''

GeG
sese

 +  Hence ).()(
'

GEe
se

−
  The proof is similar if the edge e is incident 

with the vertex 12,
13

−
+

niu
i  

Case 5:  Let the edge e be incident with the vertex u5. Let S be a strong efficient edge 

dominating set of G’. The edge e4 & e5 are the only maximum degree edges.  If the edge 

e4 belongs to S then no edge in S to strongly efficiently dominate e2. If the edge e5 

belongs to S then e2, e8, e11, …., e3n-4  belongs to S and there is no edge in S to strongly 

262



Changing and Unchanging strong efficient edge domination number of some standard 

graphs when a vertex is removed or an edge is added 

efficiently dominate e3n-2. Hence strong efficient edge dominating set does not exists. 

Proof is similar if the edge e is incident with the vertex 22,
23

−
+

niu
i . From all the 

above cases, 
( ) =)(0' GE

se  

Remark: Let n = 1, G’=K1, 3. 
).(1)'(

''
GG

sese
 ==

 Therefore 
( ) )(0' GEe

se


 

 

Theorem 2.13. 

 
Let G = P3n+1, .1n  Let e = uv be any edge incident with any vertex of G and G’ = 

G+e. Then )()(
''

GeG
sese

 =+
 
if e is incident with u2 or 11,3 − niu i  , 

21,
23

−
+

nju
j

and 1)()(
''

+=+ GeG
sese

  if e is incident with u1, u3n,  

11,
13

−
+

niu
i

 . 

Proof:
  

Let G = P3n+1, .1n V(G) = }131/{ + niui ,  niuueGE iii 31/)( 1 == + . Let e = 
uv be the any edge incident with any vertex of G and G’ = G+e. 

Case 1: Let e be an end edge of G’. Then G’ = P3n+2. Therefore 

1)()'(
23

''
+==

+
nPG

nsese


 
but .)(

'
nG

se
= Therefore ).()(

''
GeG

sese
 +  Hence 

).()(
'

GEe
se

−
  Therefore 1)()(

''
+=+ GeG

sese


 
Case 2: Let the edge e be incident with the vertex u2.  Suppose .1n S = {e2, e5, e8, …. 

e3n-1} is the unique strong efficient edge dominating sets of G’ and |S| = n. Therefore 

nGG
sese

== )()'(
''

 Hence ).()(
0'

GEe
se

  The proof is similar if the edge e is incident 

with the vertex u3n. 
 

Case 3:  Let the edge e be incident with the vertex u3. e2 and e3 are the only maximum 

degree edges. Hence any strong efficient edge dominating set contains either e2 or e3 .If 

e2 belongs to S then S = {e2, e5, e8,  …., e3n-3, e3n-1} is the unique strong efficient edge 

dominating sets of G’and |S| =n. Hence )()'(
''

GnG
sese

 == . Therefore =
+

)()(
'

GE
se

. 

If the edge e3 belongs to S then there is no edge in S to strongly efficiently dominate e3. 

The proof is similar if the edge e is incident with the vertex .12,
3

− niu
i  

Case 4:  Let the edge e be incident with the vertex u4. Then S1 = {e1, e3, e5, …. e3n-1} , 

S2 = {e2, e4, e7, …. e3n-2, e3n} are the strong efficient edge dominating sets of G’ and 

|S1|=|S2|=n+1. Therefore 1)'(
'

+= nG
se

  but .)(
'

nG
se

=
 
Therefore ).()(

''
GeG

sese
 +  

Hence ).()(
'

GEe
se

+
  The proof is similar if the edge e is incident with the vertex 

12,
13

−
+

niu
i  

Case 5:  Let the edge e be incident with the vertex u5. Let S be a strong efficient edge 

dominating set of G’. The edge e4 & e5 are the only maximum degree edges.  If the edge 

e4 belongs to S then no edge in S to strongly efficiently dominate e2. If the edge e5 

belongs to S then e2, e8, e11, …., e3n-4  belongs to S and there is no edge in S to strongly 

efficiently dominate e3n-2. Hence strong efficient edge dominating set does not exists. 

263



M. Annapoopathi and N. Meena 
 

Proof is similar if the edge e is incident with the vertex 
22,

23
−

+
niu

i . From all the
 

above cases, 
( ) =)(0' GE

se  

 

Theorem 2.14. 

 
Let G = P3n+2 .1n  Let e = uv be any edge incident with any vertex of G and G’ = 

G+e. Then )()(
''

GeG
sese

 =+
 
if e is incident with all 231/ + niu

i
 except u1, u3n 

and 1)()(
''

+=+ GeG
sese

  if e is incident with u1, u3n. 

Proof:
  

Let G = P3n+2, .1n V(G) = }231/{ + niui ,  131/)( 1 +== + niuueGE iii . Let e 
= uv be the any edge incident with any vertex of G and G’ = G+e. 

Case 1: Let e be an end edge of G’. Then G’ = P3n+3=P3(n+1). Therefore 

2)()'(
)1(3

''
+==

+
nPG

nsese


 
but .1)(

'
+= nG

se
 Therefore ).()(

''
GeG

sese
 +  Hence 

).()(
'

GEe
se

+
  Therefore 1)()(

''
+=+ GeG

sese


 
Case 2: Let the edge e be incident with the vertex u2.  Suppose .1n S = {e2, e5, e8, …. 

e3n-1, e3n+1} is the unique strong efficient edge dominating sets of G’ and |S| = n+1. 

Therefore .1)()'(
''

+== nGG
sese


 
Hence ).()(

0'
GEe

se
  The proof is similar if the 

edge e is incident with the vertex u3n. 
 

Case 3:  Let the edge e be incident with the vertex u3. e2 and e3 are the only maximum 

degree edges. Hence any strong efficient edge dominating set contains either e2 or e3 .If 

e2 belongs to S then S = {e2, e5, e8,  …., e3n-3, e3n-1, e3n+1} is the unique strong efficient 

edge dominating set of G’ and |S| = n+1. Hence )(1)'(
''

GnG
sese

 =+= . Therefore 

).()(
0'

GEe
se

  If e3 belongs to S then S = {e1, e3, e6, ….,e3n } is the unique strong 

efficient edge dominating set of G’ and |S| = n+1. Hence )(1)'(
''

GnG
sese

 =+= . 

Therefore ).()(
0'

GEe
se


 
The proof is similar if the edge e is incident with the vertex 

.12,
3

− niu
i  

Case 4:  Let the edge e be incident with the vertex u4. The edge e3 & e4 are the only 

maximum degree edges. Hence any strong efficient edge dominating set S contains 

either e3 or e4. If the edge e3 belongs to S then S = {e1, e3, e6,  ….,e3n } is the unique 

strong efficient edge dominating set of G’ and |S| = n+1. Hence )(1)'(
''

GnG
sese

 =+=

. Therefore ).()(
0'

GEe
se


 
If the edge e4 belongs to S then there is no edge in S to 

strongly efficiently dominate e3n. Hence strong efficient edge dominating set does not 

exist. The proof is similar if the edge e is incident with the vertex 12,13 −+ niu i  

Case5:  Let the edge e be incident with the vertex u5. The edge e4 & e5 are the only 

maximum degree edges. Hence any strong efficient edge dominating set S contains 

either e4 or e5.  If the edge e4 belongs to S then there is no edge in S to strongly 

efficiently dominate e2. If the edge e5 belongs to S then {e2, e5, e8,  …., e3n-3, e3n-1, 

e3n+1}} is the unique strong efficient edge dominating set of G’ and |S| = n+1. Hence 

264



Changing and Unchanging strong efficient edge domination number of some standard 

graphs when a vertex is removed or an edge is added 

)(1)'(
''

GnG
sese

 =+= . Therefore ).()(
0'

GEe
se

   Proof is similar if the edge e is 

incident with the vertex 22,
23

−
+

niu
i .  

 

Theorem 2.15. 

Let G = C3n, .1n  Let e = uv be any edge incident with any vertex of G and G’ = G+e. 

Then ).()(
''

eGG
sese

+= 
 

Proof: Let G = C3n, .1n  Let e = uv be the new edge. V(G’) = }31/,{ niuui  ,

 vueuueniuueGE
inniii

==−==
+

,,131/)'(
1331

 and G’ = G + e. Let the edge e be 

incident with the vertex u1. e1 and e3n are the maximum degree edges and they are 

adjacent. Any strong efficient dominating set contains e1 or e3n. Then S1 = {e1, e4, e7, …. 

e3n-2}, S2 = {e3, e6, e9,  …. e3n-3, e3n} are the strong efficient edge dominating sets of G’ 

and |S1|=|S2|= n, .1n .1,)'(
'

= nnG
se

  No other strong efficient edge dominating set 

exists without e1 and e3n. Therefore .1,)()(
''

=+= nneGG
sese

   The proof is similar 

if the edge e is with any niu
i

32,   

 

Theorem 2.16.  

Let G = K1, n, .1n  Let e be any edge incident with any vertex of G and G’ = G+e. 

Then ).()(
''

eGG
sese

+= 
 

Proof: Let G = K1, n, .1n Let V(G) = },1/,{ niuui   
E(G) = }.1/{ niuu

i
 V(G’) 

= }1/,,{ nivuui  .  

Case 1:  Let e be the new edge incident with u. Then G’ = K1, n+1.  Therefore 

1)()'(
''

== GG
sese

   Case2:  Let uiv be the new edge incident with ui. Then {uui} is the 

unique strong efficient edge dominating set of G’ and .1)'(
'

=G
se

  Therefore

1)()(
''

=+= eGG
sese

 .  

 

Theorem 2.17.  

Let G = Dr, s, .1, sr  Let e = xy be any edge incident with any vertex of G and G’ = 

G+e. Then 






=+

=
=

wvorwueifG

wvorwueifG
G

jise

se

se
,1)(

),(
)'(

'

'

'




 .

  

Proof: G = Dr, s, .1, sr  Let e = xy be the new edge. V(G) =

},1,1/,,,{ sjrivuvu
ji

 V(G’) = }1,1/,,,,,{ sjriyxvuvu
ji

 ,

 sjrixyevvfuvfuueGE
jjii

===== 1,1/,,,)'( . Then G’ = G+e. 

Case 1:  If the edge e is incident with either the vertex u or the vertex v. Then G’= Dr+1, 

s or G’= Dr, s+1 and 1)()'(
''

== GG
sese

   

265



M. Annapoopathi and N. Meena 
 

 Case 2:  Let the edge e be incident with the vertex ui, ri 1  or vj, sj 1 . Then S 

= {uv, uiw} or S = {uv, vjw} is the strong efficient edge dominating set of G’ and |S|=2. 

.2)'(
'

=G
se

  2)()(
''

=+= eGG
sese

 .  

 

3. Conclusions 

In this paper, the change or unchanged of the strong efficient edge domination number 

of some standard graphs are determined, when a vertex is removed or an edge is added. 

 

 

References 

 

[1] D.W. Bange, A. E. Barkauskas, L. H. Host, and P. J. Slater. Generalized 
domination and efficient domination in graphs. Discrete Math., 159:1 – 11, 1996. 

[2] D.W. Bange, A. E. Barkauskas, and P. J. Slater. Efficient dominating sets in 
graphs. In R. D. Ringeisen and F. S. Roberts, editors, Applications of Discrete 

Mathematics, pages 189 – 199. SIAM, Philadelphia, PA, 1988. 

[3] Dominngos M. Cardoso, J. Orestes Cerdefra Charles Delorme, Pedro C.Silva , 
Efficient edge domination in regular graphs, Discrete Applied Mathematics 156 , 3060 - 

3065(2008) 

[4] Teresa W. Haynes, Stephen T. Hedetniemi, Peter J. Slater (Eds), Domination in 
graphs: Advanced Topics, Marcel Decker, Inc., New York 1998. 

[5] Teresa W. Haynes, Stephen T. Hedetniemi, Peter J. Slater, Fundamentals of 
domination in graphs, Marcel Decker, Inc., New York 1998. 

[6] C. L. Lu, M-T. Ko, C. Y. Tang, Perfect edge domination and efficient edge 
domination in graphs, Discrete Appl. Math. 119227-250(2002) 

[7] S. L. Mitchell and S. T. Hedetniemi, edge domination in trees. Congr. 
Number.19489-509 (1977) 

[8] E. Sampath Kumar and L. Pushpalatha, Strong weak domination and domination 
balance in a graph, Discrete Math., 161:235 - 242, 1996. 

[9] C. Yen and R.C. T. Lee., The weighted perfect domination problem and its 
variants, Discrete Applied Mathematics, 66, p147-160, 1996. 

 

266