Ratio Mathematica                                                                            Volume 44, 2022 

 
 

 

 

 

 

Medium Domination Decomposition 

of Graphs 

 
Ebin Raja Merly E1 

Saranya J2 

 

 

Abstract 

A set of vertices 𝑆  in a graph 𝐺  dominates 𝐺  if every vertex in 𝐺  is either in 𝑆  or 
adjacent to a vertex in 𝑆. The size of any smallest dominating set is called domination 
number of 𝐺. The concept of Medium Domination Number was introduced by Vargor 
and Dunder which finds the total number of vertices that dominate all pairs of vertices 

and evaluate the average of this value. The Medium domination Number is a notation 

which uses neighbourhood of each pair of vertices. For G = (V, E) and ∀ u, v∈ V if u, v 
are adjacent they dominate each other, then atleast dom (u, v) = 1. The total number of 

vertices that dominate every pair of vertices is defined as TDV(G)=∑ dom (u, v), for 

every u, v∈ V(G). For any connected, undirected, loopless graph G of order p, the 

Medium Domination Number MD(G) = 
𝑇𝐷𝑉(𝐺)

𝑝𝐶2
. In this paper we have introduced the 

new concept Medium Domination Decomposition. A decomposition (𝐺1, 𝐺2, … , 𝐺𝑛 ) of 
a graph  G is said to be Medium Domination Decomposition (MDD) if ⌊𝑀𝐷(𝐺𝑖 )⌋ =  𝑖 −
1, 𝑖 = 1,2, . . . , 𝑛.  
 

Keywords: Domination Number, Medium Domination Number, Medium Domination 

Decomposition. 

 

Mathematical classification Number: 05C69, 54D053 

 

 
 

1 Associate Professor, Department of Mathematics, Nesamony Memorial Christian College, Marthandam. 

(Affiliated to Manonmaniam Sundaranar University, Abishekapatti, Tirunelveli - 627 012, Tamilnadu, 

India), ebinmerly@gmail.com    
2  Research Scholar (Reg. No: 20113112092022), Department of Mathematics, Nesamony Memorial 

Christian College, Martha.  (Affiliated to Manonmaniam Sundaranar University, Abishekapatti, 

Tirunelveli - 627 012, TamilNadu, India), saranyajohnrose@gmail.com 
3  Received on June 8th, 2022. Accepted on Aug 10th, 2022. Published on Nov 30th, 2022. doi: 

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

under the CC-BY licence agreement. 

59

mailto:ebinmerly@gmail.com
mailto:saranyajohnrose@gmail.com


Ebin Raja Merly E and Saranya J 

 

 

1. Introduction 

Graph is a mathematical representation of a network and it describes the 

relationship between vertices and edges. Let G = (V, E) be a simple, connected, 

undirected, loopless graph with p vertices and q edges and Gi be the subgraph of G with 

pi vertices and qi edges, where 1 ≤ i ≤ n, n is the number of subgraphs of G. The length 

of a shortest 𝑢 − 𝑣 path in a connected graph G is called the distance from a vertex 𝑢  to 
a vertex 𝑣 . 𝑑(𝑢, 𝑣)  denotes the distance between 𝑣  and 𝑢 . Two 𝑢 − 𝑣  paths are 
internally disjoint if they have no vertices in common, other than 𝑢 and 𝑣. The degree of 
a vertex 𝑣  in a graph 𝐺  is the number of edges of incident with 𝑣  and denoted by 
deg(𝑣). The minimum degree among the vertices of a graph 𝐺 is denoted by 𝛿(𝐺). The 
maximum degree among vertices of a graph 𝐺 is denoted by ∆(𝐺). [1] The concept of 
Medium Domination Number was introduced by Vargor and Dunder which finds the 

total number of vertices that dominate all pairs of vertices and evaluate the average of 

this value.[5] T.I. Joel and E.E. Merly introduced the concept of Geodetic 

Decomposition of Graphs. Motivated by the above we have introduced the new concept 

of Medium Domination Decomposition of Graphs. For basic terminologies in graph 

theorem, we refer [2], [3] and [4]. The following are the basic definitions and results 

needed for the main section. 

 

Definition 1.1. [1] For 𝐺 = (𝑉, 𝐸)  and ∀ 𝑢, 𝑣 ∈ 𝑉 , if 𝑢  and 𝑣  are adjacent they 
dominate each other, then atleast 𝑑𝑜𝑚 (𝑢, 𝑣) = 1. 
 

Definition 1.2. [1] For 𝐺 = (𝑉, 𝐸) and ∀ 𝑢, 𝑣 ∈ 𝑉 , the total number of vertices that 
dominate every pair of vertices is defined as 𝑇𝐷𝑉(𝐺) = Σ∀𝑢,𝑣∈𝑉(𝐺)𝑑𝑜𝑚 (𝑢, 𝑣). 

 

Definition 1.3. [1] For any connected, undirected, loopless graph 𝐺  of order 𝑝  the 

Medium Domination Number of 𝐺 is defined as 𝑀𝐷(𝐺) =
𝑇𝐷𝑉(𝐺)

(
𝑃
2

)
. 

 

2. Medium Domination Decomposition of Graphs 

Definition. 2.1 Let 𝐺  be a simple connected (𝑝, 𝑞)  graph. A decomposition 
(𝐺1, 𝐺2, … , 𝐺𝑛 ) of a graph 𝐺 is said to be a Medium Domination Decomposition (𝑀𝐷𝐷) 
if ⌊𝑀𝐷(𝐺𝑖 )⌋ = 𝑖 − 1, 𝑖 = 1,2,3, … . , 𝑛. 
 

 

 

 

 

 

60



Medium Domination Decomposition of Graphs 
 

Example. 2.2 

 

 

 

 

 

 

 

  

 

 

 

 

 

 

Figure 2.3 

Here 𝑀𝐷(𝐺1) = 0.8, 𝑀𝐷(𝐺2) = 1 and 𝑀𝐷(𝐺3) = 2 
That is ⌊𝑀𝐷(𝐺1)⌋ = 0, 𝑀𝐷(𝐺2) = 1 and 𝑀𝐷(𝐺3) = 2 
 

Remark. 2.4 

i) Star Graph does not admit 𝑀𝐷𝐷 
ii) 𝐾𝑝, 𝑝 ≤ 4, does not admit 𝑀𝐷𝐷 

 

Theorem. 2.5 If a graph 𝐺 admits 𝑀𝐷𝐷(𝐺1, 𝐺2, … , 𝐺𝑛), then 𝑝 ≥ 4 and 𝑞 ≥ 3. 
Proof. 

Since the Medium Domination Number is one, when 𝑝 ≤ 3  and 𝑞 ≤ 2  and the 
Medium Domination Number is two, when 𝑝 and 𝑞 is 3, we can’t get any subgraph with 
⌊𝑀𝐷(𝐺𝑖 )⌋ = 0. 
 

Note: 2.6 The converse of the above theorem is need not be true. For example, the 

complete graph 𝐾4. 
 

Theorem: 2.7 

 Let 𝐺 be a graph and 𝐺 admits 𝑀𝐷𝐷(𝐺1, 𝐺2, … , 𝐺𝑛). Then  
(i) 𝑀𝐷(𝐺2) = 𝑝2 − ∆(𝐺2) if and only if 𝐺2 is 𝐾1,𝑚 for any 𝑚. 
(ii) 𝑀𝐷(𝐺𝑖 ) = ∆(𝐺𝑖) if and only if 𝐺𝑖 is a complete graph, where 𝑖 = 2,3, … . , 𝑛 
Proof: 

 Suppose 𝐺 admits 𝑀𝐷𝐷(𝐺1, 𝐺2, … , 𝐺𝑛). 

𝑣1 𝑣2 

𝑣3 

𝑣4 𝑣5 

𝑣6 

𝐺 

𝑣1 𝑣2 𝑣3 𝑣4 

𝐺1 

𝑣2 

𝑣5 𝑣6 𝐺3 

𝑣1 

𝑣4 𝑣5 𝐺2 

61



Ebin Raja Merly E and Saranya J 

 

 

(i) Let 𝐺2 be 𝐾1,𝑚 for any 𝑚. 

 𝐺2 has 𝑝2 vertices and 𝑞2(= 𝑝2 − 1) edges and the maximum degree of 𝐺2 = 𝑝2 − 1 

 𝑀𝐷(𝐺2) =
(𝑝2−1)+(

𝑝2−1
2

)

(
𝑝2
2

)
  

 𝑀𝐷𝐷(𝐺2) = 1  
 𝑀𝐷(𝐺2) = 𝑝2 − ∆(𝐺2)  
(ii) Let 𝐺𝑖 be a complete graph, 𝑖 = 1,2,3, … , 𝑛 

 𝐺𝑖 has 𝑝𝑖 vertices and 𝑞𝑖 =
𝑝𝑖(𝑝𝑖−1)

2
 edges and the maximum degree of 𝐺𝑖 = 𝑝𝑖 − 1. 

 𝑀𝐷(𝐺𝑖 ) =
𝑝𝑖(𝑝𝑖−1)

2
+𝑝𝑖[𝑝𝑖−1)𝐶2] 

(
𝑝𝑖
2

)
  

 𝑀𝐷(𝐺𝑖 ) = 𝑝𝑖 − 1  
 𝑀𝐷(𝐺𝑖 ) = ∆(𝐺𝑖 ), 𝑖 = 2,3, … , 𝑛  
Hence the proof. 

 

Theorem: 2.8  Let 𝐺  be a graph and 𝐺  admits 𝑀𝐷𝐷(𝐺1, 𝐺2, … , 𝐺𝑛 ) . Then 

∑ ⌊𝑀𝐷(𝐺𝑖 )⌋ <
𝑛(𝑛+1)

2

𝑛
𝑖=1 ⌈𝑀𝐷(𝐺)⌉, where 𝑛 is the number of decompositions of 𝐺. 

Proof: 

We prove this theorem by induction on 𝑛. 
When 𝑛 = 1, 
Then ⌊𝑀𝐷(𝐺1)⌋ < ⌈𝑀𝐷(𝐺)⌉, 
Therefore, the result is true for 𝑛 = 1 
Assume that the theorem is true for 𝑛 − 1 

That is, ∑ ⌊𝑀𝐷(𝐺𝑖 )⌋ <
𝑛(𝑛−1)

2

𝑛−1
𝑖=1 ⌈𝑀𝐷(𝐺)⌉ 

To prove: the theorem is true for 𝑛. 

That is, ∑ ⌊𝑀𝐷(𝐺𝑖 )⌋ <
𝑛(𝑛+1)

2

𝑛
𝑖=1 ⌈𝑀𝐷(𝐺)⌉. 

Now, 

∑ ⌊𝑀𝐷(𝐺𝑖 )⌋ = ⌊𝑀𝐷(𝐺1)⌋ + ⌊𝑀𝐷(𝐺2)⌋ + ⋯ + ⌊𝑀𝐷(𝐺𝑛)⌋
𝑛−1
𝑖=1   

 ∑ ⌊𝑀𝐷(𝐺𝑖 )⌋ + ⌊𝑀𝐷(𝐺𝑛)⌋ <
𝑛(𝑛+1)

2
+ ⌈𝑀𝐷(𝐺)⌉ + ⌊𝑀𝐷(𝐺𝑛)⌋

𝑛−1
𝑖=1   

 ∑ ⌊𝑀𝐷(𝐺𝑛)⌋ <
𝑛2−𝑛

2
+ ⌊𝑀𝐷(𝐺)⌋ + ⌈𝑀𝐷(𝐺𝑛)⌉

𝑛
𝑖=1   

= (
𝑛2 − 𝑛 + 𝑛 − 𝑛

2
) ⌈𝑀𝐷(𝐺)⌉ + ⌊𝑀𝐷(𝐺𝑛)⌋ 

= (
(𝑛2 + 𝑛)

2
−

2𝑛

2
) ⌈𝑀𝐷(𝐺)⌉ + ⌊𝑀𝐷(𝐺𝑛)⌋ 

= (
𝑛2 + 𝑛

2
) ⌈𝑀𝐷(𝐺)⌉ − 𝑛⌈𝑀𝐷(𝐺)⌉ + ⌊𝑀𝐷(𝐺𝑛)⌋ 

< (
𝑛2+𝑛

2
) ⌈𝑀𝐷(𝐺)⌉, since the value of −𝑛⌈𝑀𝐷(𝐺)⌉ + ⌊𝑀𝐷(𝐺)⌋ 

is negative 

∑ ⌊𝑀𝐷(𝐺𝑛)⌋ < (
𝑛(𝑛+1)

2
) ⌊𝑀𝐷(𝐺)⌋𝑛𝑖=1   

62



Medium Domination Decomposition of Graphs 
 

The result is true for 𝑛. Hence the proof.  
 

Theorem: 2.8  If 𝐺 admits 𝑀𝐷𝐷(𝐺1, 𝐺2, … , 𝐺𝑛 ) and ∆(𝐺) = 𝑝 − 1 then 
i) 𝛾(𝐺) < ⌈𝑀𝐷(𝐺)⌉ 
ii) 𝛾(𝐺) ≤ 𝛾(𝐺𝑖 ) 
iii) 𝛾(𝐺) ≤ ⌈𝑀𝐷(𝐺𝑖 )⌉ 
Proof:  

Let 𝐺 be a graph with 𝑝 vertices and 𝑞 edges and ∆(𝐺) = 𝑝 − 1. 
Since ∆(𝐺) = 𝑝 − 1, 𝛾(𝐺) = 1. But the minimum value of ⌈𝑀𝐷(𝐺)⌉ = 1. 
Therefore 𝛾(𝐺) < ⌈𝑀𝐷(𝐺)⌉. 
The proof of (ii) and (iii) is obvious.  

 

Remark: 2.9  The equality holds in theorem 2.8, (ii) and (iii) when 𝐺𝑖 is star.  
 

Theorem: 2.10 If 𝐺 admits 𝑀𝐷𝐷(𝐺1, 𝐺2, … , 𝐺𝑛 ) then 
i) ⌈𝑀𝐷(𝐺)⌉ < 𝛾(𝐺) + ∆(𝐺) 
ii) 𝛾(𝐺𝑖 ) < 𝛾(𝐺) + ∆(𝐺) 
The Proof is obvious. 

 

Theorem: 2.11 If 𝐺  admits 𝑀𝐷𝐷(𝐺1, 𝐺2, … , 𝐺𝑛 ) and 𝐻  is a Spanning subgraph of a 
graph 𝐺, then  
(i) 𝛾(𝐺) ≤ 𝛾(𝐻) 
(ii) ⌈𝑀𝐷(𝐺)⌉ > ⌊𝑀𝐷(𝐻)⌋ 
Proof:  

Let 𝐺 be a simple connected graph and 𝐺 admits 𝑀𝐷𝐷. 
Case (i): 𝑛 = 1 
Then 𝛾(𝐺) = 𝛾(𝐻)  and ⌈𝑀𝐷(𝐺)⌉ > ⌊𝑀𝐷(𝐻)⌋.Hence the result is obvious.  
Case (ii): 𝑛 > 1 
Then, let 𝐺1, 𝐺2, … 𝐺𝑖 , … , 𝐺𝑛 be the decomposition of 𝐺. 
Let 𝐻 = 𝐺𝑖 be the spanning subgraph of 𝐺. 
Since the number of decompositions is more than one, |𝐸(𝐻)| < |𝐸(𝐺)| 
Also ∆(𝐺) ≥ ∆(𝐻) and 𝛿(𝐺) ≥ 𝛿(𝐻). 
Therefore 𝛾(𝐻) ≥ 𝛾(𝐺). 
Obviously, since 𝐻 is a spanning subgraph of 𝐺, the Medium Domination Number of 𝐻 
is less than the Medium Domination Number of 𝐺. 
Therefore ⌈𝑀𝐷(𝐺)⌉ > ⌊𝑀𝐷(𝐻)⌋. 
Hence the proof.  

 

3. Conclusion 

    In this paper, we calculated the number of vertices that are capable of dominating 

both of u and v. The total number of vertices that dominate every pair of vertices is 

examined and the average of this value is calculated which is called “the medium 

domination number” of graph. Some theorems and results on the Medium Domination 

Decomposition of a graph and basic graph classes are given. Further this concept can be 

extended to some family of graphs.  

63



Ebin Raja Merly E and Saranya J 

 

 

References 
 

[1] Duygu Vargor, Pinar Dundar, “The Medium Domination Number of a Graph”, 

International Journal of pure and applied mathematics volume of No.3, 2011 297-306. 

[2] Fairouz Beggas, “Decomposition and Domination of Some Graphs” Data Structures 

and Algorithms [cs.DS]. University Claude Bernard Lyon 1,2017. 

[3] S. Arumugan and S. Ramachandran, “Invitation to Graph Theory”, SciTech 

publications (India) PVT. LTD. (2003).  

[4] Teresa W. Haynes, Stephen T. Hedetnimi and Peter J. Slater, “Fundamentals of 

Domination in Graphs” Marcel Dekkar, Inc., New York, 1998.  

[5] T.I. Joel and E.E.R. Merly, “Geodetic Decomposition of Graphs”, Journal of 

Computer and Mathematical Sciences, 9(7) (2018), 829 - 833. 

[6] Sr Little Femilin Jana. D., Jaya. R., Arokia Ranjithkumar, M., Krishnakumar. S., 

“Resolving Sets and Dimension in Special Graphs”, Advances And Applications In 

Mathematical Sciences 21 (7) (2022), 3709-3717. 

 

          

64

https://scholar.google.com/citations?view_op=view_citation&hl=en&user=xWCP70YAAAAJ&sortby=pubdate&authuser=1&citation_for_view=xWCP70YAAAAJ:IjCSPb-OGe4C