Digital Repository @ Vidyasagar University

Vidyasagar University

Dspace @ Vidyasagar University

Departmental committee meeting held on 17.12.2019

DC Meeting in Hindi 22.01.2019

This paper deals with the simple connected graphs which have an essential domination number and unique dominating set

Chandrasekaran, V.T

Rajasri, N

Journal of Physical Sciences, Vol. 24, 2019, 91-96 
ISSN: 2350-0352 (print), www.vidyasagar.ac.in/publication/journal 
Published on 6 June 2019 
 
91 
 
Essential Domination of Some Special Graphs 
V.T. Chandrasekaran1 and N.Rajasri2 
1Department of Mathematics, Jawahar Science College  
Neyveli-607803, India. Email: vtcvtc14@gmail .com 
2Department of Mathematics, Vallalar Arts and Science College 
Vadalur-607303, India. Email: rajasri150583@gmail .com 
 
ABSTRACT 
This paper deals with the simple connected graphs which have an essential domination 
number and unique dominating set. 
 
Keywords: Domination, Essential domination, Dutch windmill graph, Pan graph, 
Complete graph, wheel graph, fan graph, lollipop graph, star graph.  
Mathematical Subject Classification (2010): 05C75 
 
1. Introduction 
In this paper a graph ( ),G V X= , a vertex u of a simple connected graph is an essential 
dominating vertex, if every minimum dominating set contains the vertex u. The minimum 
cardinality of the unique dominating set is called the essential domination number. it is 
denoted by ( ).E Gγ  Cockayne and Hedetniemi [1] introduced the concept dominating 
set. Harary, Norman and Cartwright [2] explained an interesting application in voting 
situations using the concept of domination. Liu [3]also discussed the application of 
dominance to communication network, where a dominating set represents a set of cities 
which acting as transmitting stations, can transmit messages to every city in the network. 
We also characterized the essential dominating set for the join of one vertex. In this paper 
we have found out essential domination number and unique domination set of some 
special graph. 
 
2. Preliminaries 
Definition 2.1. Let  G  be a graph. A subset S of V  is called dominating set if every 
vertex in V S− is adjacent to a vertex in S . The minimum cardinality of a dominating 
set in G  is called the domination number of G  and it is denoted by ( ).Gγ  
 
Definition 2.2. A vertex u  of a simple connected graph is an essential dominating 
vertex, if every minimum dominating set contains the vertex u . The minimum 
cardinality of the essential dominating set is called the essential domination number, it is 
denoted by ( ).E Gγ  
Definition 2.3. Dutch windmill graph: the dutch windmill graph ( )nmD  is the graph 
V.T. Chandrasekaran and N.Rajasri 
92 
 
obtained by taking n copies of the cycle mC  with vertex in common. The minimum 
cardinality of a dominating set in G  is called the domination number ofG  and it is 
denoted by ( ) ( )nmDγ  . 
Theorem 2.1.  A dutch windmill graph ( )nmD  has a essential dominating vertex set, if 
( )  0 3n mod≡ .  
Proof: Let G  be a dutch windmill graph with n  vertices. And  degv∆ = , so must be 
in the minimal dominating set. { }( ) –  nmD v  becomes a disconnected graph of 1 mnP − . 
v  is adjacent to every pendent vertices of 1mP −   in the graph { }( ) –  nmD v . Hence it 
is enough to dominate the remaining 3 3 mnP −  paths. it has unique dominating set S  with 
minimum cardinality ( ) ( )nmDγ    then every element in S  is an essential.  
 Figure 1: 
Theorem 2.2. If G is 3nP then G  has dominating vertices which are essential. 
Proof: 3nP  has only one dominating set S with minimum cardinality ( ) Gγ  then 
every element in S  is an essential vertex. 
Hence{ }2 5 8 3 1,  ,  ,  .......... nv v v v −  is an essential domination set. 
 
Corollary 2.1. For any 3 1nP +   and 3 2nP +  has no essential dominating set. 
Essential Domination of Some Special Graphs 
93 
 
Proof: A graph 3 1nP +  has more than one minimal dominating set, let 1 2,  ,......S S then 
1 2 ........S S φ∩ ∩ =   hence 3 1nP +  has no essential vertex. 
{ }1 2 3 1...........  S S S v∩ ∩ =∩  has more than one minimal dominating set, let 
1 2,  ,  ...........S S But  
 3  nV S∉  and 1 2 ........S S φ∩ ∩ ≠  hence 3 2nP +  has one essential vertex. 
 
Theorem 2.3. A pan graph  nP   has a essential dominating vertex, if  n   ( )1 3mod .  
Proof: 
Case1: ( )  1 3n mod≡  
Let G  be a pan graph, it has more than one domination set exist and all vertices have a 
chance to come in domination set. Let 1 2 3,  ,  .............S S S  where 
{ }1 1 4 7, 3 ,  ,  ......... ,  i iS v v v v v−=  &        { }2 3 6........., 4 1  ,  ,  ,  i iS v v v v v− −= and so on 
( )1 2 3 4 .............. S S S S V G∪ ∪ =∪ ∪ but 1 2 3 ...........  S S S φ∩ ∩ =∩  so it has no 
essential vertex. 
Case 2: ( ) 2 3n mod≡  
Let G  be a pan graph, it has more than one dominating set exist it has1 essential vertex 
which node is adjacent to only pendent vertex. That is { }1 2 3 1...........  S S S v∩ ∩ =∩ . 
  
              
Figure 2: 
Case 3: ( ) 0 3n mod≡  
Let G  be a pan graph, it has unique dominating set S  with minimum cardinality ( ) Gγ  
then every element in S  is an essential, where { };  S   1,2,3.......k−= =3k 2v  
Theorem 2.4. If ( )  V G n=  and   1degv n= −  with    1deg w n< −  for all 
( ) { } - w V G v∈  then v   is essential. 
Proof: Let ( )v V G∈  such that   1degv n= − , clearly { }v  is the only minimal 
V.T. Chandrasekaran and N.Rajasri 
94 
 
dominating set of G , Therefore { }v  is an essential vertex. 
 
Theorem 2.5. For any graph, if H G u= +  then u is essential in H . 
Proof: Let  G  be any graph, its may have more then one components. Le H G u= + , 
u  is adjacent to all vertices in G  So, u  has a maximum degree but  is not 
necessary essential vertex in H  because more then one maximum vertex exist in H . 
But in H ,u  is isolated so u  must be exist in minimum dominating set. Hence u  is 
on essential vertex in H  
Theorem 2.6. Let G  be a graph with  ( )Gγ  1= . 
Let ( ) [ ] ( )     / }   { GS v V G N v V G= ∈ =   then  S  is essential in G .  
Proof: If ( ) [ ] ( )     / }   { GS v V G N v V G= ∈ =   then   0degv =  in G  that is 
v  is an isolated vertex. therefore it must be in every dominating set, hence v  is 
essential vertex thus any isolated vertex thus any isolated vertex is an essential vertex 
therefore S  is essential set in G . 
 
Theorem 2.7.  Let G  be any graph and u ∈ G , if u  has atleast two pendent edges 
then u  is essential dominating vertex. 
Proof: Let G  be any graph, ( )u V G∈  and atleast  two pendent edges. u  is  must 
contain in { }S . ie, { }u S⊂ suppose, { }u S⊄  then there must exist another vertex , 
which dominates all the vertices adjacent to u . But obviously no such vertex exist. 
Hence u  is essential dominating vertex in G . 
 
Theorem 2.8. Let G  be a   nK  graph and v G∈ . Let H   be a graph obtained from 
G  by adding any vertex u and adjacent to v   then H  has essential domination set. 
Proof: Let G  be a  nK  graph, in  nK  all vertices has degree  1n −  therefore there 
exist no essential vertex. Let  H  be a graph obtained from G  by adding any vertex u  
And adjacent to v  now H  has 1n +  vertices and degv  is n  and degu  is one all 
other vertices has degree 1n −  clearly  v  is the only minimal dominating set of  H . 
Therefore  v  is an essential vertex. In H  has disconnected graph (only two component) 
first component degv  is zero ie,  v   is isolated vertex therefore  v  is essential 
dominating vertex. And another one is star graph   1degu n= −  ie, u  is essential 
dominating vertex, since  H  has essential dominating set.  
 
3. The number of essential dominating vertices in the given graph is the essential 
dominating set.  
WHEEL GRAPH:( )nw  
Essential Domination of Some Special Graphs 
95 
 
( )3 1wγ =  has more than one minimal dominating set hence w3 has no essential vertex. 
• Wheel graph ( )nw , ( ) 1.E nwγ =  where 3n >  only one minimal dominating 
set { }w . and hence w  is essential 
              
Figure 3: 
• STAR GRAPH( )nS , ( ) 1.E nSγ =  
For 1n > , nS  have only one minimal dominating set { }v . Hence v  is essential 
vertex. 
• FAN GRAPH nF ,  
 
  2 3,F F  no essential vertex 
  nF  3n > ,v  is essential vertex.  Example for 5F                                    
  nK  Graph ,
 
( ) .nE nKγ =   
Lollipop graph 
The ( ),m n  lollipop graph is a graph obtained by joining a complete graph mK   to a 
path nP  on n   vertices and its denoted by ,m nL . In a lollipop graph with the path nP  
where   3 2n n= −  has essential dominating set. Like that, Bi-star, friendship graph, 
flower graph, windmill graph,3 nP …theses all are having essential domination set. 
 
Result 3.1. Let  G  be a ,m nK  graph and  v G∈ . Let  H  be a graph obtained from G  
by adding any vertex u  and adjacent tov . if  m n=  then u  is essential in H . And  
then H  has no essential domination vertex. And if   m n≠ , Let H be a graph obtained 
from G  by adding any vertex u  and adjacent to ( )uδ then u  is essential in H . 
But H  has no essential vertex.  
 
4. Conclusion  
In this article, we have discussed few special graphs for which the domination is 
 
W    
    
W     
V.T. Chandrasekaran and N.Rajasri 
96 
 
Essential. Further research can be done in exploring various graphs with the same 
property 
REFERENCES 
1. E.J.Cockayne and S.P. Hedetniemi, Towards a Theory of Domination in Graphs, 
Networks, 7 (1977) 247-261. 
2. F. Harary, Robert Z. Norman and Dorwin Cartwright, An Introduction to the Theory of 
Directed Graphs by Newyork: John. Wiley and Sons. 1967 
3. C. L. Liu Introduction to Combinatorial mathematics, McGraw-Hill, 1968 Newyork. 
4. S.Hamid, S.Balamurugan and A. Navaneethankrishnan, A note on isolate domination 
in graphs, Electronic Journal of Graph Theory and Applications, 4(1) (2016) 94-100. 
5. V.T Chandrasekaran and N.Rajasri, Minimum diameter spanning tree, American 
Journal of  Computational Mathematics, 8 (2018) 203– 208. 
6. A.Gallian, Dynamic survey DS6: Graph labeling, Electronic .Combinatorics, DS6, 
(2007) 1-58. 
 
 
 
 
 
 
 


Essential Domination of Some Special Graphs

Women's Studies (M.Phil.) Question Papers, 2019

Applied Mathematics Question Papers, 2019

Resolutions of the Research Advisory Committee Meeting (Sociology) held on 17.07.2019

D C Meeting of History Dated 07.08.2019

Minutes of the Departmental Committee Meeting (Electronics) held on 30.01.19

Minutes of the Departmental Committee Meeting (Electronics) held on 29.02.19

Minutes of the Teachers students committee meeting (Bio-Medical Laboratory Science and Management) held on 01/03/2019