Ratio Mathematica                                                                  Volume 44, 2022 

 

 

 

 

 

Steiner domination decomposition number of 

graphs 

 
Mahiba M1 

Ebin Raja Merly E2 

 

 

Abstract 

In this paper, we introduce a new concept Steiner domination decomposition number of 

graphs. Let 𝐺 be a connected graph with Steiner domination number𝛾𝑠(𝐺).  A 

decomposition 𝜋 = {𝐺1, 𝐺2, … , 𝐺𝑛 } of 𝐺 is said to be a Steiner Domination Decomposition 
(𝑆𝐷𝐷) if 𝛾𝑠 (𝐺𝑖 ) = 𝛾𝑠(𝐺), 1 ≤ 𝑖 ≤ 𝑛. Steiner domination decomposition number of 𝐺 is the 

maximum cardinality obtained for an 𝑆𝐷𝐷 of 𝐺 and is denoted as 𝜋𝑠𝑡𝑑 (𝐺). Bounds on 

𝜋𝑠𝑡𝑑 (𝐺) are presented. Also, few characteristics of the subgraphs belonging to 𝑆𝐷𝐷 of 

maximum cardinality are discussed.  

 

Keywords: subgraphs; domination; decomposition number. 

 

AMS subject classification: 05C12, 05C693 

 

 

 

 

 

 

 
1Research Scholar (Reg.No: 20213112092013), Research Department of Mathematics, Nesamony 

Memorial Christian College, Marthandam-629165. Affiliated to Manonmaniam Sundaranar University, 

Tirunelveli-627012, Tamil Nadu, India. mahibakala@gmail.com 
2Associate Professor, Research Department of Mathematics, Nesamony Memorial Christian College, 

Marthandam-629165. Affiliated to Manonmaniam Sundaranar University, Tirunelveli-627012, Tamil 

Nadu, India. ebinmerly@gmail.com 
3Received on June 18th, 2022. Accepted on Aug 10th, 2022. Published on Nov30th, 2022. doi: 

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

under the CC-BY license agreement. 

 

100

mailto:mahibakala@gmail.com
mailto:ebinmerly@gmail.com


Mahiba. M and Ebin Raja Merly. E 

 

 

1. Introduction 

Let 𝐺 be a simple, connected and undirected graph with vertex set 𝑉(𝐺)and edge set 
𝐸(𝐺). The order and size of 𝐺 are 𝑝 and 𝑞 respectively. For standard terminologies and 
notations, we refer to [1]. Steiner domination number of a graph is a concept introduced 

by John 𝑒𝑡 𝑎𝑙. Further studies on this concept is found in [7], [8]. In [5], we introduced 
the concept of Steiner decomposition number of graphs and in [6] we presented the 

Steiner decomposition number of Complete 𝑛 − Sun graph. In this paper, a new 
decomposition concept called Steiner domination decomposition number of graphs is 

studied. The following are the basic definitions and results needed for the subsequent 

section. 

 

Definition 1.1. [2] Let 𝐺 be a connected graph. For a set 𝑊 ⊆ 𝑉(𝐺), a tree 𝑇 contained 
in 𝐺 is a Steiner tree with respect to 𝑊 if 𝑇 is a tree of minimum order with 𝑊 ⊆
𝑉(𝑇). The set 𝑆(𝑊) consists of all vertices in 𝐺 that lie on some Steiner tree with 
respect to 𝑊. The set 𝑊 is a Steiner set for 𝐺 if 𝑆(𝑊) = 𝑉(𝐺). The minimum 
cardinality among the Steiner sets of 𝐺 is the Steiner number 𝑠(𝐺). 
 

Definition 1.2. [3] A set 𝐷 ⊆ 𝑉(𝐺)in a graph 𝐺 is called a dominating set if every 
vertex 𝑣 ∈ 𝑉(𝐺) is either an element of 𝐷 or is adjacent to an element of 𝐷. The 
domination number 𝛾(𝐺) is the minimum cardinality of a dominating set of 𝐺. 
 

Definition 1.3. [4] For a connected graph 𝐺, 𝑊 ⊆ 𝑉(𝐺)is called a Steiner dominating 
set if 𝑊 is both a Steiner set and a dominating set. The minimum cardinality of a Steiner 
dominating set of 𝐺 is said to be Steiner domination number and is denoted by 𝛾𝑠(𝐺). A 
Steiner dominating set of cardinalities𝛾𝑠(𝐺) is said to be a 𝛾𝑠 − 𝑠𝑒𝑡 of 𝐺. 
 

Definition 1.4. The decomposition 𝜋 of a graph 𝐺 is a collection of edge disjoint 
subgraphs 𝐺1, 𝐺2 , … , 𝐺𝑛 such that each 𝐺𝑖 , 1 ≤ 𝑖 ≤ 𝑛is connected and 𝐸(𝐺) = 𝐸(𝐺1) ∪
E(𝐺2) ∪ … ∪ E(𝐺𝑛).  
 

Definition 1.5. [5] For a connected graph 𝐺 with Steiner number 𝑠(𝐺), a decomposition 
𝜋 = {𝐺1, 𝐺2 , … , 𝐺𝑛}of 𝐺 is said to be a Steiner Decomposition(𝑆𝐷) if 𝑠(𝐺𝑖 ) = 𝑠(𝐺) for 
all 𝑖, (1 ≤ 𝑖 ≤ 𝑛).The maximum cardinality obtained for the Steiner decomposition 𝜋 of 
𝐺 is called the Steiner decomposition number of 𝐺 and is denoted by 𝜋𝑠𝑡 (𝐺). Steiner 
decomposition of cardinality 𝜋𝑠𝑡 (𝐺) is denoted as 𝑆𝐷𝑚𝑎𝑥 .  
 

Theorem 1.6. [4] For any connected graph 𝐺 of order 𝑝 ≥ 2, 𝛾𝑠(𝐺) = 2 if and only if 
there exists a Steiner dominating set 𝑊 = {𝑢, 𝑣}of 𝐺 such that 𝑑(𝑢, 𝑣) ≤ 3. 
 

Theorem 1.7. [4] For a connected graph 𝐺 of order 𝑝 ≥ 2,  𝛾𝑠(𝐺) = 𝑝 if and only if 
𝐺 = 𝐾𝑝. 

 

Result 1.8. [7] For the path graph on 𝑝 vertices (𝑝 ≥ 2), 𝛾𝑠(𝑃𝑝) =

101



Steiner domination decomposition number of graphs 

 

{
⌈

𝑝−4

3
⌉ + 2         𝑖𝑓 𝑝 ≥ 5    

          2                𝑖𝑓 𝑝 = 2,3,4
 

 

Notation 1.9. ℱ𝑝 denotes the family of trees of order 𝑝 with the property that each 

vertex is either a pendant vertex or a support vertex. 

 

2. Steiner Domination Decomposition 

Definition 2.1. A decomposition 𝜋 = {𝐺1, 𝐺2 , … , 𝐺𝑛}of a graph 𝐺 is called a Steiner 
Domination Decomposition (𝑆𝐷𝐷) if 𝛾𝑠(𝐺𝑖)=𝛾𝑠(𝐺), (1 ≤ 𝑖 ≤ 𝑛). The maximum 
cardinality obtained for 𝜋 is called the Steiner domination decomposition number of 𝐺 
and is denoted by 𝜋𝑠𝑡𝑑 (𝐺). An 𝑆𝐷𝐷 of cardinality 𝜋𝑠𝑡𝑑 (𝐺)is denoted as 𝑆𝐷𝐷𝑚𝑎𝑥 . A 
graph 𝐺 with 𝜋𝑠𝑡𝑑 (𝐺) = 1 is said to be non-Steiner domination decomposable graph. If 
𝜋𝑠𝑡𝑑 (𝐺) ≥ 2 then 𝐺 is said to be Steiner domination decomposable graph. 
 

Example 2.2. Consider the graph 𝐺 in figure 1. 

 

Figure 1. Graph 𝐺 and its Steiner domination decomposition 𝜋 = {𝐺1, 𝐺2} 

The set 𝑊 = {𝑣1, 𝑣2 , 𝑣5, 𝑣9}is a 𝛾𝑠 − 𝑠𝑒𝑡 of 𝐺. Hence 𝛾𝑠(𝐺) = 4. Since 𝛾𝑠(𝐺1) =
𝛾𝑠(𝐺2) = 4 = 𝛾𝑠(𝐺), 𝜋 = {𝐺1, 𝐺2} is a 𝑆𝐷𝐷. It can be easily verified that 𝜋 is a 
𝑆𝐷𝐷𝑚𝑎𝑥 . Thus 𝜋𝑠𝑡𝑑 (𝐺) = 2. 
 

Theorem 2.3.  If 𝜋𝑠𝑡𝑑 (𝐺) = 𝑞 then 𝑑𝑖𝑎𝑚 𝐺 < 4. 
Proof. Steiner domination decomposition number of 𝐺, 𝜋𝑠𝑡𝑑 (𝐺) = 𝑞 ⟺ 𝜋 =
{𝐺𝑖 ≅ 𝐾2 /1 ≤ 𝑖 ≤ 𝑞} is a 𝑆𝐷𝐷𝑚𝑎𝑥 . Steiner domination number of 𝐾2 is , hence 

𝛾𝑠(𝐺) = 2. Also, we have 𝛾𝑠(𝐺) = 2 implies 𝑑𝑖𝑎𝑚 𝐺 < 4. Therefore if 𝜋𝑠𝑡𝑑 (𝐺) =
𝑞 then 𝑑𝑖𝑎𝑚 𝐺 < 4. Hence proved. 
 

Theorem 2.4.  Let 𝐺 be a connected graph with 𝛾𝑠(𝐺) ≥ 3. Then 1 ≤ 𝜋𝑠𝑡𝑑 (𝐺) ≤

102



Mahiba. M and Ebin Raja Merly. E 

 

⌊
𝑞

𝛾𝑠(𝐺)
⌋. 

Proof. From definition 2.1, it is obvious that 𝜋𝑠𝑡𝑑 (𝐺) ≥ 1. Let 𝜋 = {𝐺𝑖 /1 ≤ 𝑖 ≤ 𝑛}  be 
a 𝑆𝐷𝐷 of 𝐺. First to prove |𝐸(𝐺𝑖 )| ≥ 𝛾𝑠(𝐺) for all 𝑖. Assume to the contrary that 
|𝐸(𝐺𝑖 )| < 𝛾𝑠(𝐺) for some 𝑖. Without loss of generality, let |𝐸(𝐺1)| < 𝛾𝑠(𝐺). Then 
|𝑉(𝐺1)| ≤ 𝛾𝑠(𝐺). 
Case (i):|𝑉(𝐺1)| < 𝛾𝑠 (𝐺) 
If |𝑉(𝐺1)| < 𝛾𝑠(𝐺) then 𝛾𝑠(𝐺1) < 𝛾𝑠(𝐺). Therefore 𝐺1 ∉ 𝜋. 
Case (ii): |𝑉(𝐺1)| = 𝛾𝑠(𝐺) 
In order to satisfy 𝛾𝑠 (𝐺1) = 𝛾𝑠(𝐺), 𝐺1 must be a complete graph on 𝛾𝑠(𝐺)vertices. But 
we have |𝑉(𝐺1)| > |𝐸(𝐺1)|. Hence 𝐺1 is non isomorphic to 𝐾𝛾𝑠(𝐺). Therefore 𝐺1 ∉ 𝜋. 

In both the cases, we arrive at a contradiction to our assumption that 𝐺1 ∈ 𝜋. Hence 
|𝐸(𝐺1)| ≥ 𝛾𝑠(𝐺). Since 𝐺1 is chosen arbitrarily, we can conclude |𝐸(𝐺𝑖 )| ≥ 𝛾𝑠(𝐺) for 
all 𝑖.Thus subgraphs of 𝐺 belonging to any Steiner domination decomposition should 

have atleast 𝛾𝑠(𝐺)edges and so 𝜋𝑠𝑡𝑑 (𝐺) ≤ ⌊
𝑞

𝛾𝑠(𝐺)
⌋. Hence 1 ≤ 𝜋𝑠𝑡𝑑 (𝐺) ≤ ⌊

𝑞

𝛾𝑠(𝐺)
⌋. 

 

Theorem 2.5. Let 𝐺 be a Steiner domination decomposable graph with 𝑞 edges. For 

𝛾𝑠(𝐺) = 3, 𝜋𝑠𝑡𝑑 (𝐺) =
𝑞

3
if and only if each 𝐺𝑖 ∈ 𝑆𝐷𝐷𝑚𝑎𝑥 is isomorphic to either 𝐾1,3or 

𝐾3 and for 𝛾𝑠(𝐺) > 3, 𝜋𝑠𝑡𝑑 (𝐺) =
𝑞

𝛾𝑠(𝐺)
 if and only if each 𝐺𝑖 ∈ 𝑆𝐷𝐷𝑚𝑎𝑥 is isomorphic to 

𝐾1,𝛾𝑠(𝐺). 

Proof. Let 𝐺 be a Steiner domination decomposable graph. Assume 𝛾𝑠(𝐺) = 3 and 

𝜋𝑠𝑡𝑑 (𝐺) =
𝑞

3
. Then for any 𝐺𝑖 ∈ 𝑆𝐷𝐷𝑚𝑎𝑥 , |𝐸(𝐺𝑖 )| = 3 and hence|𝑉(𝐺𝑖 )| ≤ 4. If 

|𝑉(𝐺𝑖 )| ≤ 3 for some 𝑖, then the only graph that satisfies 𝛾𝑠(𝐺𝑖 ) = 3 is 𝐾3. If |𝑉(𝐺𝑖 )| =
4 for some 𝑖, then 𝐺𝑖 is a tree. Star graph 𝐾1,3 is the unique tree which satisfies the 

required properties. Thus if 𝜋𝑠𝑡𝑑 (𝐺) =
𝑞

3
 then 𝐺𝑖 ≅ 𝐾1,3or 𝐾3 for all 𝐺𝑖 ∈

𝑆𝐷𝐷𝑚𝑎𝑥 . Converse part is obvious. Now, assume𝛾𝑠(𝐺) > 3and 𝜋𝑠𝑡𝑑 (𝐺) =
𝑞

𝛾𝑠(𝐺)
.Then|𝐸(𝐺𝑖 )| = 𝛾𝑠(𝐺) for every 𝐺𝑖 ∈ 𝑆𝐷𝐷𝑚𝑎𝑥 and so |𝑉(𝐺𝑖 )| ≤ 𝛾𝑠(𝐺) + 1. There 

doesn't exist any graph 𝐺𝑖 with the properties |𝑉(𝐺𝑖 )| ≤ 𝛾𝑠(𝐺) and 𝛾𝑠(𝐺𝑖 ) = 𝛾𝑠(𝐺). 
Since 𝐾1,𝛾𝑠(𝐺) is the unique graph on 𝛾𝑠(𝐺) + 1 vertices that has Steiner domination 

number same as 𝐺, we have |𝑉(𝐺𝑖 )| = 𝛾𝑠(𝐺) + 1 implies 𝐺𝑖 ≅ 𝐾1,𝛾𝑠(𝐺). Hence if 

𝜋𝑠𝑡𝑑 (𝐺) =
𝑞

𝛾𝑠(𝐺)
 then 𝐺𝑖 ≅ 𝐾1,𝛾𝑠(𝐺) for all 𝐺𝑖 ∈ 𝑆𝐷𝐷𝑚𝑎𝑥 . Converse is obvious.  

 

Theorem 2.6. Let 𝐺 be a connected graph with 𝛾𝑠(𝐺) ≥ 3 and ⌊
𝑞

𝛾𝑠(𝐺)
⌋ = 𝑚, (𝑚 > 1). If 

𝜋𝑠𝑡𝑑 (𝐺) = 𝑚 − 𝑛 , (0 ≤ 𝑛 < 𝑚 − 1) then 𝛾𝑠(𝐺) ≤ |𝐸(𝐺𝑖 )| ≤ (𝑛 + 2)𝛾𝑠(𝐺) − 1 for all 
𝐺𝑖 ∈ 𝑆𝐷𝐷𝑚𝑎𝑥 . 

Proof. Let 𝐺 be a connected graph such that 𝛾𝑠(𝐺) ≥ 3 . Let ⌊
𝑞

𝛾𝑠(𝐺)
⌋ = 𝑚, (𝑚 > 1). 

Assume 𝜋𝑠𝑡𝑑 (𝐺) = 𝑚 − 𝑛 where 0 ≤ 𝑛 < 𝑚 − 1. Let 𝜋 = {𝐺1, 𝐺2 , … , 𝐺𝑚−𝑛}be a 
𝑆𝐷𝐷𝑚𝑎𝑥 of 𝐺. To prove 𝛾𝑠(𝐺) ≤ |𝐸(𝐺𝑖 )| ≤ (𝑛 + 2)𝛾𝑠(𝐺) − 1 for all 𝐺𝑖 ∈ 𝜋. The 
requirement of edges in each subgraph belonging to any 𝑆𝐷𝐷 of 𝐺 is atleast 𝛾𝑠(𝐺). 
Hence|𝐸(𝐺𝑖 )| ≥ 𝛾𝑠(𝐺)for every 𝐺𝑖 ∈ 𝜋. Without loss of generality, assume 

103



Steiner domination decomposition number of graphs 

 

|𝐸(𝐺𝑚−𝑛)| ≥ |𝐸(𝐺𝑖 )|, 1 ≤ 𝑖 ≤ 𝑚 − (𝑛 + 1). Since⌊
𝑞

𝛾𝑠(𝐺)
⌋ = 𝑚, we get 𝑚𝛾𝑠(𝐺) ≤ 𝑞 ≤

(𝑚 + 1)𝛾𝑠(𝐺) − 1. We know that ∑ |𝐸(𝐺𝑖 )| = 𝑞 
𝑚−𝑛
𝑖=1 and |𝐸(𝐺𝑖 )| ≥ 𝛾𝑠(𝐺)for 1 ≤ 𝑖 ≤

𝑚 − (𝑛 + 1).  
 

Therefore,          

∑ |𝐸(𝐺𝑖 )| ≤ (𝑚 + 1)𝛾𝑠(𝐺) − 1

𝑚−𝑛

𝑖=1

 

(𝑚 − (𝑛 + 1))𝛾𝑠(𝐺) + |𝐸(𝐺𝑚−𝑛)| ≤ (𝑚 + 1)𝛾𝑠(𝐺) − 1 
⇒ |𝐸(𝐺𝑚−𝑛)| ≤ (𝑛 + 2)𝛾𝑠(𝐺) − 1 
Thus, the possible number of edges in a subgraph belonging to 𝑆𝐷𝐷𝑚𝑎𝑥 is atmost 
(𝑛 + 2)𝛾𝑠(𝐺) − 1. Hence 𝛾𝑠(𝐺) ≤ |𝐸(𝐺𝑖 )| ≤ (𝑛 + 2)𝛾𝑠(𝐺) − 1  for all 𝐺𝑖 ∈ 𝑆𝐷𝐷𝑚𝑎𝑥 . 
 

Theorem 2.7. Let 𝐺 be a connected graph with 𝛾𝑠(𝐺) ≥ 5 and ⌊
𝑞

𝛾𝑠(𝐺)
⌋ = 𝑚, (𝑚 > 1). If 

𝜋𝑠𝑡𝑑 (𝐺) = 𝑚 − 𝑛 , (0 ≤ 𝑛 < 𝑚 − 1) then the number of path graphs belonging to 
𝑆𝐷𝐷𝑚𝑎𝑥 is strictly less than 𝑛 + 1. 
Proof. Let 𝐺 be a connected graph with 𝑞 edges. Let 𝛾𝑠(𝐺) = 𝑘 + 1 where 𝑘 ≥
4. Assume𝜋𝑠𝑡𝑑 (𝐺) = 𝑚 − 𝑛, (0 ≤ 𝑛 < 𝑚 − 1).Let 𝜋 = {𝐺𝑖 /1 ≤ 𝑖 ≤ 𝑚 − 𝑛}  be a 
𝑆𝐷𝐷𝑚𝑎𝑥 . Let 𝑁 denotes the number of path graphs belonging to 𝜋. First we try to 
prove 𝑁 ≠ 𝑛 + 1.  
Suppose 𝑁 = 𝑛 + 1. Consider 𝐺1, 𝐺2 , … , 𝐺𝑛+1 ∈ 𝜋 as path graphs. Path graphs with 
Steiner domination number 𝑘 + 1 are 𝑃3𝑘−1, 𝑃3𝑘and 𝑃3𝑘+1. Therefore  3𝑘 − 2 ≤
|𝐸(𝐺𝑖 )| ≤ 3𝑘 for 1 ≤ 𝑖 ≤ 𝑛 + 1. 
Now, ∑ |𝐸(𝐺𝑖 )|

𝑚−𝑛
𝑖=1 = ∑ |𝐸(𝐺𝑖 )|

𝑛+1
𝑖=1 + ∑ |𝐸(𝐺𝑖 )|

𝑚−𝑛
𝑖=𝑛+2  

≥ (𝑛 + 1)(3𝑘 − 2) + (𝑚 − 2𝑛 − 1)(𝑘 + 1) 

∑ |𝐸(𝐺𝑖 )|

𝑚−𝑛

𝑖=1

≥ (𝑛 + 2)𝑘 − (4𝑛 + 3) + 𝑚(𝑘 + 1) 

For 𝑘 ≥ 4, 𝑞 ≤ (𝑚 + 1)(𝑘 + 1) − 1 < (𝑛 + 2)𝑘 − (4𝑛 + 3) + 𝑚(𝑘 + 1). . 
This is a contradiction since ∑ |𝐸(𝐺𝑖 )| = 𝑞 

𝑚−𝑛
𝑖=1 and 𝑞 ≤ (𝑚 + 1)(𝑘 + 1) − 1. Hence 

𝑁 ≠ 𝑛 + 1. If 𝑁 > 𝑛 + 1 then ∑ |𝐸(𝐺𝑖 )| > (𝑛 + 2)𝑘 − (4𝑛 + 3) + 𝑚(𝑘 + 1).  
𝑚−𝑛
𝑖=1 This 

again results in a contradiction. Thus 𝑁 < 𝑛 + 1 and so number of path graphs 
belonging to 𝜋 is strictly less than 𝑛 + 1. Hence the proof. 
 

Theorem 2.8. If 𝑇 ∈ ℱ𝑝 then 𝜋𝑠𝑡𝑑 (𝑇) = 1. 

Proof. Assume 𝑇 ∈ ℱ𝑝 . Every vertex of 𝑇 is either a pendant vertex or a support vertex. 

Let 𝑙 and 𝑚 be the number of pendant vertices and support vertices of 𝑇 respectively. 
Clearly the set of all pendant vertices of 𝑇 forms the 𝛾𝑠 − 𝑠𝑒𝑡. Hence 𝛾𝑠(𝑇) = 𝑙. 
Number of edges of 𝑇 is 𝑙 + 𝑚 − 1. Also, 𝑚 ≤ 𝑙 for any graph. Hence by theorem 2.4, 
𝜋𝑠𝑡𝑑 (𝑇) = 1. 
 

Remark 2.9. If 𝑠(𝐺) = 𝛾𝑠(𝐺) then 𝜋𝑠𝑡 (𝐺)need not be equal to 𝜋𝑠𝑡𝑑 (𝐺). 

104



Mahiba. M and Ebin Raja Merly. E 

 

 

Figure 2. Graph 𝐺 and its 𝑆𝐷𝐷𝑚𝑎𝑥 , 𝜋 = {𝐺1, 𝐺2} 

For the graph 𝐺 in figure 2, minimum Steiner set= 𝛾𝑠 − 𝑠𝑒𝑡 = {𝑣1, 𝑣6, 𝑣8, 𝑣11}. 
Hence 𝑠(𝐺) = 𝛾𝑠(𝐺) = 4. Steiner domination decomposition 𝜋 = {𝐺1, 𝐺2}is a 𝑆𝐷𝐷𝑚𝑎𝑥  
of 𝐺 and so 𝜋𝑠𝑡𝑑 (𝐺) = 2. Also 𝜋𝑠𝑡 (𝐺) = 1. Therefore 𝜋𝑠𝑡 (𝐺) ≠ 𝜋𝑠𝑡𝑑 (𝐺). 
 

Theorem 2.10. Let 𝐺 be a connected graph such that 𝑠(𝐺) = 𝛾𝑠(𝐺) = 𝑘 (𝑠𝑎𝑦). If there 
exist some 𝑆𝐷𝑚𝑎𝑥 and 𝑆𝐷𝐷𝑚𝑎𝑥  for 𝐺 satisfying the condition that each subgraph in the 
decompositions is of order 𝑘 + 1 and has a cutvertex of degree 𝑘 then 𝜋𝑠𝑡 (𝐺) =
𝜋𝑠𝑡𝑑 (𝐺). 
Proof. Consider a connected graph 𝐺 with 𝑠(𝐺) = 𝛾𝑠(𝐺) = 𝑘. Let 𝜋1 and 𝜋2 be the 
𝑆𝐷𝑚𝑎𝑥  and 𝑆𝐷𝐷𝑚𝑎𝑥 respectively which satisfies the condition that each subgraph in both 
the decompositions is of order 𝑘 + 1 and has a cutvertex of degree 𝑘. First to prove, 
𝜋1is a 𝑆𝐷𝐷. Let 𝜋1 = {𝐺𝑖  /1 ≤ 𝑖 ≤ 𝑛 }. 𝜋1is a 𝑆𝐷 implies 𝑠(𝐺𝑖 ) = 𝑘 for all 𝑖. Each 
𝐺𝑖 (1 ≤ 𝑖 ≤ 𝑛 )is of order 𝑘 + 1 and has a cutvertex of degree 𝑘.Therefore minimum 
Steiner set of 𝐺𝑖 = 𝛾𝑠 − 𝑠𝑒𝑡 of 𝐺𝑖 for all 𝑖 and so 𝛾𝑠(𝐺𝑖 ) = 𝑘. Thus 𝜋1 is a 𝑆𝐷𝐷. In the 
similar way, we can prove 𝜋2 is a 𝑆𝐷. Now to prove, 𝜋𝑠𝑡 (𝐺) = 𝜋𝑠𝑡𝑑 (𝐺). Suppose 
𝜋𝑠𝑡 (𝐺) > 𝜋𝑠𝑡𝑑 (𝐺) then |𝜋1| > |𝜋2|. Since 𝜋1 is a 𝑆𝐷𝐷, we get a contradiction to 𝜋2 is 
a𝑆𝐷𝐷𝑚𝑎𝑥 . Suppose 𝜋𝑠𝑡 (𝐺) < 𝜋𝑠𝑡𝑑 (𝐺) then |𝜋1| < |𝜋2|. Since 𝜋2 is a 𝑆𝐷, we get a 
contradiction to 𝜋1 is a 𝑆𝐷𝑚𝑎𝑥 . Therefore 𝜋𝑠𝑡 (𝐺) = 𝜋𝑠𝑡𝑑 (𝐺). 

 

3. Conclusion 

In this paper, we initiate a study on Steiner domination decomposition number of 

graphs. It is quite interesting to investigate this new parameter and study the properties 

of the subgraphs belonging to 𝑆𝐷𝐷. Future works can be done on calculating the Steiner 

105



Steiner domination decomposition number of graphs 

 

domination decomposition number for families of graphs and finding the bounds in 

terms of other graph theoretical parameters. 

 

References 
 

[1] J.A. Bondy and U.S.R. Murty, Graph Theory with Applications, Macmillan Press, 

London, 1976. 

[2] G. Chartrand and P. Zhang, The Steiner number of a graph, Discrete Mathematics, 

242, pp.41-54, 2002. 

[3] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in 

Graphs, CRC press, 2013. 

[4] J. John, G. Edwin and P.A.P. Sudhahar, The Steiner domination number of a graph, 

International Journal of Mathematics and Computer Applications Research, 3(3), pp.37-

42, 2013. 

[5] E. E. R. Merly and M. Mahiba, Steiner decomposition number of graphs, Malaya 

Journal of Matematik, Special Issue, pp.560-563, 2021. 

[6] E. E. R. Merly and M. Mahiba, Steiner Decomposition Number of Complete𝑛 − 
Sun graph, Journal of Physics: Conference series,1947, 2021. 

[7] K. Ramalakshmi and K. Palani, On Steiner Domination Number of Graphs, 

International Journal of Mathematics Trends and Technology, 41(2), pp.186-190, 2017. 

[8] S.K. Vaidya and R.N. Mehta, On Steiner domination in graphs, Malaya Journal of 

Matematik, 6(2), pp.381-384, 2018. 

[9] 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. 

 

 

106

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