Ratio Mathematica                                                                            Volume 44, 2022 

 
 

 

Connected  𝟐 − Dominating Sets and 
Connected 𝟐 −  Domination Polynomials of the 

Complete Bipartite Graph 𝒌𝟐,𝒎. 
 

Y. A. Shiny1 

T. Anithababy2 

 
 

Abstract 

Let 𝐺 = (𝑉, 𝐸) be a simple graph. Let 𝐷𝑐2  (𝐺, 𝑗) be the family of connected 

2−dominating sets in 𝐺 with cardinality 𝑗 and 𝑑𝑐2 (𝐺, 𝑗) = |𝐷𝑐2 (𝐺, 𝑗)|. Then the 

polynomial 𝐷𝑐2 (𝐺, 𝑥) = ∑ 𝑑𝑐2 (𝐺, 𝑗)𝑥
𝑗 ,

|𝑉(𝐺)|

𝑗=𝛾𝑐2 (𝐺)
 is called the 2−domination polynomial 

of 𝐺 where 𝛾𝑐2 (𝐺) is the connected 2− domination number of 𝐺.Let 𝐷𝑐2 (𝑘2,𝑚,𝑗) be the 

family of connected 2−dominating sets of the Complete bipartite graph 𝑘2,𝑚 with 

cardinality 𝑗 and let 𝑑𝑐2 (𝑘2,𝑚,𝑗) = |𝐷𝑐2 (𝑘2,𝑚,𝑗) |. Then the connected 2− domination 

polynomial  𝐷𝑐2 (𝑘2,𝑚,𝑥) of 𝑘2,𝑚 is defined as 𝐷𝑐2 (𝑘2,𝑚,𝑥) = ∑ 𝑑𝑐2 (𝑘2,𝑚,𝑗)𝑥
𝑗 ,

|𝑉(𝑘2,𝑚)|

𝑗=𝛾𝑐2 (𝑘2,𝑚)
   

where 𝛾𝑐2 (𝑘2,𝑚,𝑗) is the connected 2 – domination number of 𝑘2,𝑚,. In this paper, we 

obtain a recursive formula for  𝑑𝑐2 (𝑘2,𝑚,𝑗).Using this recursive formula, we construct 

the connected 2−domination polynomial  𝐷𝑐2 (𝑘2,𝑚,𝑥) =

∑ 𝑑𝑐2 (𝑘2,𝑚,𝑗)𝑥
𝑗 , where𝑚+2𝑗=3 𝑑𝑐2 (𝑘2,𝑚,𝑗) is the number of connected 2−dominating sets 

of   𝑘2,𝑚 of cardinality 𝑗 and some properties of this polynomial have been studied. 
 

Keywords: Dominating, Connected and cardinality 

 

2010 Mathematical classification number: 05C69, 54D053. 
 
 
 
 

 
1Reg. No.: 19213042092006, Research Scholar (Full time), Research Department of Mathematics, 

Women’s Christian College, Nagercoil. Affiliated by Manonmaniam Sundaranar University, Tamil Nadu, 

India, shinyjebalin@gmail.com  
2Assistant Professor, Research Department of Mathematics, Women’s Christian College, Nagercoil. 

Affiliated by Manonmaniam Sundaranar University, Tamil Nadu, India. anithasteve@gmail.com 
3Received on June 7th, 2022. Accepted on Aug 10th, 2022. Published on Nov 30th, 2022. doi: 

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

under the CC-BY licence agreement. 

51

mailto:anithasteve@gmail.com


Y. A. Shiny
 
and T. Anithababy

 

 

1. Introduction 

        Let G = (V, E) be a simple graph of order, |V| = m. For any vertex vϵV, the open 
neighbourhood of v is the set N(v) = {uϵV/uvϵE} and the closed neighbourhood of V is 
the set 𝑁[𝑣] = 𝑁(𝑣) ∪  {𝑣}. For a set 𝑆 ⊆ 𝑉, the open neighbourhood of 𝑆 is 𝑁(𝑆) =
𝑈𝑣𝜖𝑠𝑁(𝑣) and the closed neighbourhood of S is 𝑁(𝑆) ∪ 𝑆.A set 𝐷 ⊆ 𝑉 is a dominating 
set of 𝐺, if 𝑁[𝐷] = 𝑉 or equivalently, every vertex in 𝑉 − 𝐷 is adjacent to atleast one 
vertex in 𝐷.The domination number of a graph 𝐺 is defined as the cardinality of a 
minimum dominating set 𝐷 of vertices in 𝐺 and is denoted by 𝛾(𝐺). A dominating set 𝐷 
of 𝐺 is called a connected dominating set if the induced sub-graph < 𝐷 > is connected. 
The connected domination number of a graph 𝐺 is defined as the cardinality of a 
minimum connected dominating set 𝐷 of vertices in 𝐺 and is denoted by 𝛾𝑐 (𝐺). 

A graph 𝐺 = (𝑉, 𝐸)is called a bipartite graph if its vertices 𝑉 can be partitioned into 
two subsets 𝑉1 and  𝑉2 such that each edge of 𝐺 connects a vertex of  𝑉 1to a vertex of 
 𝑉2. If 𝐺 contains every edge joining a vertex of 𝑉1 and a vertex of   𝑉2 then 𝐺 is called a 
complete bipartite graph. It is denoted by 𝑘𝑚,𝑛, where 𝑚 and 𝑛 are the numbers of 
vertices in 𝑉1 and  𝑉2 respectively. Let 𝑘2,𝑚 be the Complete bipartite graph with 𝑚 + 2 
vertices. Throughout this paper let us take     𝑉(𝑘2,𝑚) = {𝑣1,𝑣2,𝑣3,...,𝑣𝑚+1,𝑣𝑚+2}  and  

𝐸(𝑘2,𝑚) = {(𝑣1, 𝑣3),( 𝑣1, 𝑣4), (𝑣1,𝑣5),…, (𝑣1, 𝑣𝑚+1), (𝑣1, 𝑣𝑚+2), (𝑣2, 𝑣3),( 𝑣2, 𝑣4),  

( 𝑣2, 𝑣5),…, (𝑣2, 𝑣𝑚+1), (𝑣2, 𝑣𝑚+2). 

As usual we use (
𝑚
𝑗 ) for the combination 𝑚 to 𝑗. Also, we denote the set 

{1, 2, … … … ,2𝑚 − 1, 2𝑚} by [2𝑚], throughout this paper. 
 

 

2. Connected 2 – Dominating Sets of the Complete 

Bipartite Graph 𝒌𝟐,𝒎 

In this section, we state the connected 2 – domination number of the complete 

bipartite graph k2,m and some of its properties.    
 

Definition 2.1. Let 𝐺 be a simple graph of order 𝑚 with no isolated vertices. A subset 
 𝐷  ⊆  𝑉   is a 2− dominating set of the graph 𝐺 if every vertex 𝑣 𝜖 𝑉 − 𝐷 is adjacent to 
atleast two vertices in 𝐷. A 2− dominating set is called a connected 2− dominating set 
if the induced subgraph <𝐷> is connected. 
 

Definition 2.2. The cardinality of a minimum connected 2 – dominating sets of 𝐺 is 
called the connected 2 – domination number of 𝐺 and is denoted by 𝛾𝐶2 (𝐺). 

 

 Lemma 2.3 For all 𝑚 ∈ 𝑧+, (
𝑚
𝑗 )  = 0   if 𝑗 > 𝑚 or 𝑗 < 0. 

 

Theorem 2.4       𝑑𝑐2(𝑘2,𝑚, 𝑗) = {(
𝑚 + 2

𝑗
) − (

𝑚 + 1
𝑗

) − (
𝑚

𝑗 − 1)  for 3 ≤ 𝑗 ≤ 𝑚 + 2 

52



Connected  2 − Dominating Sets and Connected 2 −   Domination Polynomials of the 

Complete Bipartite Graph 𝑘2,𝑚. 

 

 
 

Proof: Let the partite sets of 𝑘2,𝑚 be 𝑉1 ={𝑣1,𝑣2,} and 𝑉2 = {𝑣3,𝑣4,,...,𝑣𝑚+1,𝑣𝑚+2}. 
Since the subgraph induced by the vertex set as {𝑣1,𝑣2, }  is not connected, every 
connected 2 −dominating set of  𝑘2,𝑚 must contain the vertex {𝑣1} or {𝑣2}  or {𝑣1,𝑣2,}. 
When 3≤ 𝑗 ≤ 𝑚, every connected 2 −dominating set must contain {𝑣1,𝑣2,}. Since, 

|𝑉(𝑘2,𝑚) | = 𝑚 + 2, 𝑘2,𝑚 contains (
𝑚 + 2

𝑗
) number of subsets of cardinality 𝑗. Since, 

the subgraphs induced by {𝑣1,𝑣2,} and {𝑣3,𝑣4,,...,𝑣𝑚+1,𝑣𝑚+2} are not connected, each 

time  (
𝑚 + 1

𝑗
) number of subsets of 𝑘2,𝑚 of cardinality j and (

𝑚
𝑗 − 1) number of subsets 

of 𝑘2,𝑚 of cardinality 𝑗 − 1 are not connected 2 −dominating sets. Hence,  𝑘2,𝑚 

contains (
𝑚 + 2

𝑗
) − (

𝑚 + 1
𝑗

) − (
𝑚

𝑗 − 1) number of subsets of connected 2 

−dominating sets, when 3≤ 𝑗 ≤ 𝑚. 

Therefore, 𝑑𝑐2(𝑘2,𝑚, 𝑗) =  (
𝑚 + 2

𝑗
) − (

𝑚 + 1
𝑗

) − (
𝑚

𝑗 − 1) for all 3≤ 𝑗 ≤ 𝑚. 

When the cardinality is 𝑚 + 1, every subset of 𝑘2,𝑚  containing {𝑣1} or {𝑣2}  are 
connected 2 −dominating sets. Therefore, two more sets are connected 2 −dominating 
sets when the cardinality is  𝑚 + 1 . 

Hence, 𝑑𝑐2(𝑘2,𝑚, 𝑗) =  (
𝑚 + 2

𝑗
) − (

𝑚 + 1
𝑗

) − (
𝑚

𝑗 − 1) + 2 , when 𝑗 = 𝑚 + 1. 

Since, there is only one subset of 𝑘2,𝑚 with cardinality 𝑚 + 2 and that set is a connected 

2 −dominating set. we get 𝑑𝑐2(𝑘2,𝑚, 𝑗) =  (
𝑚 + 2

𝑗
) when 𝑗 = 𝑚 + 2. 

 

Theorem 2.5. Let 𝑘2,𝑚 be the complete bipartite graph with 𝑚 ≥ 3. Then 
(i) 𝑑𝑐2(𝑘2,𝑚, 𝑗) =  𝑑𝑐2(𝑘2,𝑚−1, 𝑗)  +   𝑑𝑐2(𝑘2,𝑚−1, 𝑗 − 1)   
(ii) 𝑑𝑐2(𝑘2,𝑚, 𝑗) =  𝑑𝑐2(𝑘2,𝑚−1, 𝑗)  +   1 if  𝑗 = 3. 
(iii) 𝑑𝑐2(𝑘2,𝑚, 𝑗) =  𝑑𝑐2(𝑘2,𝑚−1, 𝑗)  +   𝑑𝑐2(𝑘2,𝑚−1, 𝑗 − 1)  − 2 if 𝑗 = 𝑚. 
Proof: 

(i) By Theorem 2.4, we have, 

𝑑𝑐2(𝑘2,𝑚, 𝑗) =  (
𝑚 + 2

𝑗
) − (

𝑚 + 1
𝑗

) − (
𝑚

𝑗 − 1)  for all 3 ≤ 𝑗 ≤ 𝑚 + 2. 

𝑑𝑐2(𝑘2,𝑚−1, 𝑗) =  (
𝑚 + 1

𝑗
) − (

𝑚
𝑗 ) − (

𝑚 − 1
𝑗 − 1

)   

𝑑𝑐2(𝑘2,𝑚−1, 𝑗 − 1) =  (
𝑚 + 1
𝑗 − 1

) − (
𝑚

𝑗 − 1) − (
𝑚 − 1
𝑗 − 2

)  . 

Consider, 𝑑𝑐2(𝑘2,𝑚−1, 𝑗) + 𝑑𝑐2(𝑘2,𝑚−1, 𝑗 − 1) =  (
𝑚 + 1

𝑗
) − (

𝑚
𝑗 ) − (

𝑚 − 1
𝑗 − 1

) +

                                                                                          (
𝑚 + 1
𝑗 − 1

) − (
𝑚

𝑗 − 1) − (
𝑚 − 1
𝑗 − 2

)  . 

= (
𝑚 + 1

𝑗
) + (

𝑚 + 1
𝑗 − 1

) − [(
𝑚
𝑗 ) + (

𝑚
𝑗 − 1)] – [(

𝑚 − 1
𝑗 − 1

) + (
𝑚 − 1
𝑗 − 2

)] 

53



Y. A. Shiny
 
and T. Anithababy

 

 

 =  (
𝑚 + 2

𝑗
) − (

𝑚 + 1
𝑗

) − (
𝑚

𝑗 − 1). 

  = 𝑑𝑐2(𝑘2,𝑚, 𝑗)  . 
Therefore,  
𝑑𝑐2(𝑘2,𝑚, 𝑗) =  𝑑𝑐2(𝑘2,𝑚−1, 𝑗)  +   𝑑𝑐2(𝑘2,𝑚−1, 𝑗 − 1)  for all 4≤ 𝑗 ≤ 𝑚 + 2  and 𝑗 ≠ 𝑚. 

(i) When 𝑗 = 3, 𝑑𝑐2(𝑘2,𝑚, 3) = (
𝑚 + 2

3
) − (

𝑚 + 1
3

) − (
𝑚
2

)  by Theorem 2.4 

 =   (
𝑚 + 1

2
) − (

𝑚
2

)      

 =  (
𝑚
1

)  

Consider, 𝑑𝑐2(𝑘2,𝑚−1, 3) =  (
𝑚 + 1

3
) − (

𝑚
3

) − (
𝑚 − 1

2
)  = (

𝑚
2

) − (
𝑚 − 1

2
)   

= (
𝑚 − 1

1
) 

= 𝑚 − 1. 
That is,   𝑑𝑐2(𝑘2,𝑚−1, 3)  =  𝑑𝑐2(𝑘2,𝑚, 3) − 1. 
Therefore, 𝑑𝑐2(𝑘2,𝑚 , 3)  =  𝑑𝑐2(𝑘2,𝑚−1, 3) + 1. 
Hence, 𝑑𝑐2(𝑘2,𝑚, 𝑗)  =  𝑑𝑐2(𝑘2,𝑚−1, 𝑗) + 1 𝑖𝑓 𝑗 = 3. 
(ii) When 𝑗 = 𝑚, 

 𝑑𝑐2(𝑘2,𝑚, 𝑚) =  (
𝑚 + 2

𝑚
) − (

𝑚 + 1
𝑚

) −  (
𝑚

𝑚 − 1
),   by Theorem 2.2. 

=  (
𝑚 + 1
𝑚 − 1

) − (
𝑚

𝑚 − 1
).   

= (
𝑚

𝑚 − 2
).   

Consider,  𝑑𝑐2(𝑘2,𝑚−1, 𝑚)  +   𝑑𝑐2(𝑘2,𝑚−1, 𝑚 − 1) =  (
𝑚 + 1

𝑚
) − (

𝑚
𝑚

) −  (
𝑚 − 1
𝑚 − 1

) +

2 +   (
𝑚 + 1
𝑚 − 1

) − (
𝑚

𝑚 − 1
) −  (

𝑚 − 1
𝑚 − 2

)      

= (
𝑚 + 1

𝑚
) − (

𝑚 + 1
𝑚 − 1

) −  [(
𝑚
𝑚

) + (
𝑚

𝑚 − 1
)] – [(

𝑚 − 1
𝑚 − 1

) + (
𝑚 − 1
𝑚 − 2

)] +2 

=  (
𝑚 + 2

𝑚
) − (

𝑚 + 1
𝑚

) −  (
𝑚

𝑚 − 1
) + 2 

= (
𝑚 + 1
𝑚 − 1

) −  (
𝑚

𝑚 − 1
) + 2 

=  (
𝑚

𝑚 − 2
) + 2. 

= 𝑑𝑐2(𝑘2,𝑚, 𝑚)  + 2. 
Therefore, 𝑑𝑐2(𝑘2,𝑚 , 𝑚) =  𝑑𝑐2(𝑘2,𝑚−1, 𝑚) +  𝑑𝑐2(𝑘2,𝑚−1, 𝑚 − 1) + 2. 
Hence, 𝑑𝑐2(𝑘2,𝑚, 𝑗)  =  𝑑𝑐2(𝑘2,𝑚−1, 𝑗) +  𝑑𝑐2(𝑘2,𝑚−1, 𝑗 − 1) − 2 when 𝑗 = 𝑚. 

 

3. Connected 2 −Domination Polynomials of the 
Complete Bipartite Graph 𝒌𝟐,𝒎. 

Definition 3.1. Let 𝑑𝑐2(𝑘2,𝑚, 𝑗) be the number of connected 2 –dominating sets of the 
Complete bipartite Graph 𝑘2,𝑚 with cardinality 𝑗.Then, the connected 2 − domination 

54



Connected  2 − Dominating Sets and Connected 2 −   Domination Polynomials of the 

Complete Bipartite Graph 𝑘2,𝑚. 

 

 
 

Polynomial of 𝑘2,𝑚 is defined as  𝐷𝑐2 (𝑘2,𝑚,𝑥) = ∑ 𝑑𝑐2 (𝑘2,𝑚,j)𝑥
𝑗 ,

|𝑉(𝑘2,𝑚)|

𝑗=𝛾𝑐2 (𝑘2,𝑚)
 where   

𝛾𝑐2 (𝑘2,𝑚) is the connected 2 – domination number of  𝑘2,𝑚. 

 

Remark 3.2     𝛾𝑐2 (𝑘2,𝑚) =3. 

Proof.  Let 𝑘2,𝑚 be the complete bipartite graph with partite sets 𝑉1 ={𝑣1,𝑣2} and 𝑉2 =

{𝑣3,𝑣4,,...,𝑣𝑚+1,𝑣𝑚+2}. Let  𝑣1,𝑣2𝜖 V (𝑘2,𝑚) and 𝑣1,𝑣2 are adjacent to all the other 
vertices  𝑣3,𝑣4,...,𝑣𝑚+1,𝑣𝑚+2 of 𝑘2,𝑚. Also Since, 𝑣1 and 𝑣2 are not connected, every 
connected 2 –dominating set must contain the vertices  𝑣1,𝑣2 and one more vertex from 
{𝑣3, 𝑣4,...,𝑣𝑚+1,𝑣𝑚+2}. Therefore, the minimum cardinality is 3. Hence,  𝛾𝑐2   (𝑘2,𝑚) =3. 

 

Theorem 3.3 Let 𝑘2,𝑚 be the complete bipartite graph with 𝑚 ≥ 3. 

Then 𝐷𝑐2(𝑘2,𝑚,𝑥)=(1 + 𝑥) 𝐷𝑐2(𝑘2,𝑚−1,𝑥)+𝑥
3 − 2𝑥𝑚. 

Proof: 

From the definition of connected 2 − domination Polynomial, we have, 

𝐷𝑐2(𝑘2,𝑚,𝑥)  = ∑ 𝑑𝑐2 (𝑘2,𝑚,j)𝑥
𝑗𝑚+2

𝑗=3 .                    

= 𝑑𝑐2(𝑘2,𝑚, 3)𝑥
3 + ∑ 𝑑𝑐2 (𝑘2,𝑚,j)𝑥

𝑗𝑚−1
𝑗=4 + 𝑑𝑐2 (𝑘2,𝑚,𝑚)𝑥

𝑚  +  ∑ 𝑑𝑐2 (𝑘2,𝑚,j)𝑥
𝑗𝑚+2

𝑗=𝑚+1 . 

= [𝑑𝑐2 (𝑘2,𝑚−1,3) + 1]𝑥
3 + ∑  [𝑑𝑐2 (𝑘2,𝑚−1,j)

𝑚+2

𝑗=4

+ 𝑑𝑐2 𝑘2,𝑚−1, 𝑗 − 1]𝑥
𝑗  

  +[𝑑𝑐2 (𝑘2,𝑚−1,𝑚) + 𝑑𝑐2 (𝑘2,𝑚−1,𝑚 − 1)−2]𝑥
𝑚  , by Theorem 2.5 

= 𝑑𝑐2(𝑘2,𝑚−1, 3)𝑥
3 + 𝑥3 + ∑ 𝑑𝑐2 (𝑘2,𝑚−1,j)

𝑚+2
𝑗=4 𝑥

𝑗   

                                                                       + ∑ 𝑑𝑐2 (𝑘2,𝑚−1,j − 1)
𝑚+2
𝑗=4 𝑥

𝑗 − 2𝑥𝑚. 

= ∑ 𝑑𝑐2 (𝑘2,𝑚−1,j)
𝑚+2
𝑗=3 𝑥

𝑗  +𝑥 ∑ 𝑑𝑐2 (𝑘2,𝑚−1,j − 1)
𝑚+2
𝑗=4 𝑥

𝑗−1 + 𝑥3 − 2𝑥𝑚. 

= 𝐷𝑐2(𝑘2,𝑚−1,𝑥) +𝑥𝐷𝑐2(𝑘2,𝑚−1,𝑥)+ 𝑥
3 − 2𝑥𝑚 . 

 Hence, 𝐷𝑐2(𝑘2,𝑚,𝑥)  = (1 + 𝑥)𝐷𝑐2(𝑘2,𝑚−1,𝑥) +𝑥
3 − 2𝑥𝑚,  for every 𝑚 ≥ 3. 

 

Example 3.4 Let 𝑘2,7  be the complete bipartite graph with order 9 as given in Figure 
2.1. 

𝑘2,7 : 

 
                 Figure 2.1 

    𝐷𝑐2 (𝐾2,6,𝑥) = 6𝑥
3 + 15𝑥4+20𝑥5 + 15𝑥6 + 8𝑥7 + 𝑥8. 

55



Y. A. Shiny
 
and T. Anithababy

 

 

By Theorem 3.3, we have, 

𝐷𝑐2 (𝐾2,7,𝑥) = (1 + 𝑥)( 6𝑥
3+15𝑥4+20𝑥5+15𝑥6+8𝑥7+𝑥8)+ 𝑥3 − 2𝑥7. 

= 6𝑥3+15𝑥4+20𝑥5+15𝑥6+8𝑥7+𝑥8 +6𝑥4+15𝑥5+20𝑥6+15𝑥7+8𝑥8+𝑥9 + 𝑥3 − 2𝑥7. 
= 7𝑥3+21𝑥4+35𝑥5+35𝑥6+21𝑥7+9𝑥8+𝑥9 
We obtain 𝑑𝑐2 (𝑘2,𝑚,𝑗) for 3≤ 𝑚 ≤ 15 and 3≤ 𝑗 ≤ 15 as shown in Table 1.           

 

𝑗 
𝑚 

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 

3 0 3 5 1             

4 0 4 6 6 1            

5 0 5 10 10 7 1           

6 0 6 15 20 15 8 1          

7 0 7 21 35 35 21 9 1         

8 0 8 28 56 70 56 28 10 1        

9 0 9 36 84 126 126 84 36 11 1       

10 0 10 45 120 210 252 210 120 45 12 1      

11 0 11 55 165 330 462 462 330 165 55 13 1     

12 0 12 66 220 495 792 924 792 495 220 66 14 1    

13 0 13 78 286 715 1287 1716 1716 1287 715 286 78 15 1   

14 0 14 91 364 1001 2002 3003 3432 3003 2002 1001 364 91 16 1  

15 0 15 105 455 1365 3003 5005 6435 6435 5005 3003 1365 455 107 17 1 

Table 1.𝑑𝑐2 (𝑘2,𝑚,𝑗), the number of connected 2− dominating sets of 𝑘2,𝑚   with 

cardinality 𝑗. 
 

In the following Theorem, we obtain some properties of 𝑑𝑐2 (𝐾2,𝑚,𝑗). 
 

Theorem: 3.5 The following properties hold for the coefficients of 𝐷𝑐2 (𝐾2,𝑚,𝑥) for all 

m. 

(i) 𝑑𝑐2 (𝑘2,𝑚,3) = 𝑚, for all 𝑚 ≥ 3. 

(ii) 𝑑𝑐2 (𝑘2,𝑚,𝑚 + 2) = 1, for all 𝑚 ≥ 3. 

(iii) 𝑑𝑐2 (𝑘2,𝑚,𝑚 + 1) = 𝑚 + 2 , for all 𝑚 ≥ 3. 

(iv) 𝑑𝑐2 (𝑘2,𝑚,𝑚) = (
𝑚 + 2

2
) − (

𝑚 + 1
1

) − 𝑚. 

(v) 𝑑𝑐2 (𝑘2,𝑚,𝑚 − 1) = (
𝑚 + 2

3
) − (

𝑚 + 1
2

) − (
𝑚
2

)  , for all 𝑚 ≥ 4. 

(vi) 𝑑𝑐2 (𝑘2,𝑚,𝑚 − 2) = (
𝑚 + 2

4
) − (

𝑚 + 1
3

) − (
𝑚
3

)  , for all 𝑚 ≥ 5. 

(vii) 𝑑𝑐2 (𝑘2,𝑚,𝑚 − 3) = (
𝑚 + 2

5
) − (

𝑚 + 1
4

) − (
𝑚
4

)  , for all 𝑚 ≥ 6. 

56



Connected  2 − Dominating Sets and Connected 2 −   Domination Polynomials of the 

Complete Bipartite Graph 𝑘2,𝑚. 

 

 
 

(viii) 𝑑𝑐2 (𝑘2,𝑚,𝑚 − 𝑖) = (
𝑚 + 2
𝑖 + 2

) − (
𝑚 + 1
𝑖 + 1`

) − (
𝑚
𝑖

)  , for all 𝑚 ≥ 4 and 𝑖 ≥ 1. 

Proof: 

(i)  𝑑𝑐2 (𝑘2,𝑚,3) = 𝑚. 

We prove this by induction on m. 

When 𝑚 = 3 , 𝑑𝑐2 (𝑘2,𝑚,3) = 3. 

Therefore, the result is true for 𝑚 = 3. 
Now, suppose that the result is true for all numbers less than ‘m’ and we prove it for m. 

By Theorem 2.6, 

𝑑𝑐2 (𝑘2,𝑚,3) = 𝑑𝑐2 (𝑘2,𝑚−1,3) + 1 = 𝑚 − 1 + 1 = 𝑚. 

(ii) 𝑑𝑐2 (𝑘2,𝑚,𝑚 + 2) = 1, for all 𝑚 ≥ 3. 

Since, there is only one connected 2− dominating set of cardinalities 
𝑚 +  2,  𝑑𝑐2 (𝑘2,𝑚,𝑚 + 2) = 1. 

(iii) 𝑑𝑐2 (𝑘2,𝑚,𝑚 + 1) = 𝑚 + 2 , for all m≥4. 

Since, 𝑑𝑐2 (𝑘2,𝑚,𝑚 + 1) = {[𝑚 + 2]−𝑥/𝑥𝜀[𝑚 + 2]},we have the result. 

(iv), (v), (vi), (vii) and (viii) follows from Theorem 2.4. 

 

4. Conclusion 

In this paper, the connected 2− domination polynomials of the complete bipartite 
graph 𝐾2,𝑚  has been derived by identifying its connected 2− dominating sets. It also 
helps us to characterize the connected. Connected 2− dominating sets of cardinality j. 
We can generalize this study to any of complete bipartite graph 𝐾𝑛,𝑚   and some 
interesting properties can be obtained. 

 

References 
 

[1] Alikhani. S, peng. Y. H.” Introduction to Domination Polynomial of a Graph,” Ars  

Combinatoria, Available as arxiv:0905.2251|v| [math.co]14 May 2009. 

[2] Alikhani. S, and Hamzeh Torabi,” On Domination Polynomials of Complete Partite 

Graphs” World Applied Sciences Journal,9(1):23−24,2010. 

[3] Sahib. Sh. Kahat. Abdul Jalil M. Khalaf and Roslan Hasni,” Dominating sets and 

Domination Polynomials of Wheels”. Asian Journal of Applied Sciences (ISSN:2321− 
0893), volume 02− Issue 03, June 2014. 

[4] Sahib Shayyal Kahat, Abdul Jalil M. Khalaf and Roslan Hasni,” Dominating sets 

and Domination Polynomials of Stars”. Australian Journal of Basics and Applied 

Science,8(6) June 2014, pp 383−386. 

[5] A. Vijayan, T. Anithababy, G. Edwin,” Connected Total Dominating Sets and  

57



Y. A. Shiny
 
and T. Anithababy

 

 

Connected Total Domination Polynomials of Stars and Wheels”, IOSR Journal of 

Mathematics, Volume II, pp 112−121. 

[6] A. Vijayan, T. Anithababy, G. Edwin, “Connected Total Dominating Sets and 

Connected Total Domination Polynomials of Fan Graphs 𝐹2,𝑛". International Journal of 
Mathematical Sciences and Engineering Applications (IJMSEA), Vol.10, No.1(April 

2016), pp.135−146, ISSN:0473 −9424. 

 

58