# Construction of Dominating Sets of Certain Graphs

Authors: Saeid Alikhani; Yee-Hock Peng
Journal: Journal of Discrete Mathematics
 (2013)

---

## Abstract

LetG be a simple graph. A set S⊆V is a dominating set of G, if every vertex in V∖S is adjacent to at least one vertex in S. We denote the family of dominating sets of a graph G with cardinality i by 𝒟(G,i). In this paper we introduce graphs with specific constructions, which are denoted by G(m). We construct the dominating sets of G(m) by dominating sets of graphs G(m−1), G(m−2), and G(m−3). As an example of G(m), we consider 𝒟(Pn,i). As a consequence, we obtain the recursive formula for the number of dominating sets of G(m).


---

## Body

## 1. Introduction

LetG=(V,E) be a graph of order |V|=n. For any vertex v∈V, the open neighborhood of v is the set N(v)={u∈Vuv∈E}, and the closed neighborhood is the set N[v]=N(v)∪{v}. For a set S⊆V, the open neighborhood is N(S)=⋃v∈S‍N(v), and the closed neighborhood is N[S]=N(S)∪S. A set S⊆V is a dominating set if N[S]=V, or equivalently, every vertex in V∖S is adjacent to at least one vertex in S. The domination numberγ(G) is the minimum cardinality of a dominating set in G, and the family of γ-sets is denoted by Γ(G). For a detailed treatment of this parameter, the reader is referred to [1]. Let 𝒟(G,i) be the family of dominating sets of a graph G with cardinality i, and let d(G,i)=|𝒟(G,i)|. The domination polynomialD(G,x) of G is defined as D(G,x)=∑i=γ(G)|V(G)|‍d(G,i)xi, where γ(G) is the domination number of G.The domination polynomial of a graph has been introduced by Alikhani in his Ph.D. thesis [2]. More recently it has been investigated with respect to special graphs, zeros, and application in network reliability; see [2–9].Obviously study of the dominating sets of graphs is a method for finding the coefficients of the domination polynomial of graphs. Authors studied the construction of dominating sets of some families of graphs to study their domination polynomials; see [10–13].  In this paper we would like to study some further results of this kind.In the next section we introduce graphs with specific construction which is denoted byG(m). As examples of these graphs, in Section 3 we study the dominating sets of paths and some other graphs. As a consequence, we give a recurrence relation for |𝒟(G(m),i)| and D(G(m),x).As usual we use⌈x⌉, ⌊x⌋ for the smallest integer greater than or equal to x and the largest integer less than or equal to x, respectively. In this paper we denote the set {1,2,…,n} simply by [n].


## 2. Dominating Sets of GraphsG(m)

Apath is a connected graph in which two vertices have degree 1, and the remaining vertices have degree 2. Let Pn be the path with V(Pn)=[n] and E(Pn)={(1,2),(2,3),…,(n-1,n)}; see Figure 1(a).(a) The pathPn; (b) graph G contains a simple path of length k.
(a)
(b)In this section we introduce graphs with specific construction and study their dominating sets. LetPm+1 be a path with vertices labeled by y0,y1,…,ym, for m≥3. Let G(m) be a graph obtained from G by identifying a vertex of G with an end vertex y0 of Pm+1. For example, if G is a path P2, then G(m)=P2(m) is a path Pm+2.We need some lemmas and theorems to obtain main results in this section.Lemma 1.
𝒟
(
G
(
m
)
,
i
)
=
∅ if and only if i>|V(G(m))| or i<γ(G(m)).Proof.
It follows from the definition of dominating set of graph.We recall the following theorem.Theorem 2 (see [14]).
Ife∈E(G), then γ(G-e)-1≤γ(G)≤γ(G-e).The following lemma follows from Theorem2.Lemma 3.
For anym∈N, γ(G(m-1))≤γ(G(m))≤γ(G(m-1))+1.Lemma 4 (see [15, page 371]).
The domination number of path isγ(Pn)=⌈n/3⌉.Asimple path is a path where all its internal vertices have degree two. In Figure 1(b), we have shown a graph G which contains a simple path of length k with vertices labeled 1,…,k,k+1. The following lemma follows from Lemma 4.Lemma 5.
If a graphG contains a simple path of length 3k-1, then every dominating set of G must contain at least k vertices of the path.Lemma 6.
IfY∈𝒟(G(m-4),i-1), and there exists x∈{y1,y2,…,ym}, such that Y∪{x}∈𝒟(G(m,i)), then Y∈𝒟(G(m-3),i-1).Proof.
Suppose thatY∉𝒟(G(m-3),i-1). Since Y∈𝒟(G(m-4),i-1), Y contains at least one vertex labeled ym-5 or ym-4. If ym-4∈Y, then Y∈𝒟(G(m-3),i-1), a contradiction. Hence, ym-5∈Y. But then in this case, Y∪{x}∉𝒟(G(m),i), for any x∈{y1,y2,…,ym}, also a contradiction.Lemma 7.
(i) If𝒟(G(m-1),i-1)=𝒟(G(m-3),i-1)=∅, then 𝒟(G(m-2),i-1)=∅.
(ii) If𝒟(G(m-1),i-1)≠∅,𝒟(G(m-3),i-1)≠∅ then, 𝒟(G(m-2),i-1)≠∅.
(iii) If𝒟(G(m-1),i-1)=𝒟(G(m-2),i-1)=𝒟(G(m-3),i-1)=∅, then 𝒟(G(m),i)=∅.Proof.
(i) Since𝒟(G(m-1),i-1)=𝒟(G(m-3),i-1)=∅, by Lemmas 1 and 3, i-1>|V(G(m-1))| or i-1<γ(G(m-3)). In either case we have 𝒟(G(m-2),i-1)=∅.
(ii) Suppose that𝒟(G(m-2),i-1)=∅, so by Lemma 1, we have i-1>|V(G(m-2))| or i-1<γ(G(m-2)). If i-1>|V(G(m-2))|, then i-1>|V(G(m-3))|, and hence, 𝒟(G(m-3),i-1)=∅, a contradiction. So we have i-1<γ(G(m-2),i-1), and hence, 𝒟(G(m-1),i-1)=∅, also a contradiction.
(iii) Suppose that𝒟(G(m),i)≠∅. Let Y∈𝒟(G(m),i), then at least one vertex labeled ym or ym-1 is in Y. If ym∈Y, then by Lemma 5, at least one vertex labeled ym-1,ym-2 or ym-3 is in Y. If ym-1∈Y or ym-2∈Y, then Y-{ym}∈𝒟(G(m-1),i-1), a contradiction. If ym-3∈Y, then Y-{ym}∈𝒟(G(m-2),i-1), a contradiction. Now suppose that ym-1∈Y, then by Lemma 5, at least one vertex labeled ym-2,ym-3 or ym-4 is in Y. If ym-2∈Y or ym-3∈Y, then Y-{ym-1}∈𝒟(G(m-2),i-1), a contradiction. If ym-4∈Y, then Y-{ym-1}∈𝒟(G(m-3),i-1), a contradiction. Therefore 𝒟(G(m),i)=∅.Lemma 8.
Suppose that𝒟(G(m),i)≠∅, then(i)
𝒟(G(m-1),i-1)=𝒟(G(m-2),i-1)=∅ and 𝒟(G(m-3),i-1)≠∅ if and only if γ(G(m-3))+1≤i<γ(G(m-2))+1,(ii)
𝒟(G(m-2),i-1)=𝒟(G(m-3),i-1)=∅ and 𝒟(G(m-1),i-1)≠∅ if and only if i=|V(G(m))|,(iii)
𝒟(G(m-1),i-1)=∅,𝒟(G(m-2),i-1)≠∅ and 𝒟(G(m-3),i-1)≠∅ if and only if γ(G(m-2))+1≤i<γ(G(m-1))+1,(iv)
𝒟(G(m-1),i-1)≠∅,𝒟(G(m-2),i-1)≠∅ and 𝒟(G(m-3),i-1)=∅ if and only if i=|V(G(m))|-1,(v)
𝒟(G(m-1),i-1)≠∅,𝒟(G(m-2),i-1)≠∅ and 𝒟(G(m-3),i-1)≠∅ if and only if γ(G(m-1))+1≤i≤|V(G(m))|-2.Proof.
(i) (⇒) Since 𝒟(G(m-1),i-1)=𝒟(G(m-2),i-1)=∅, by Lemmas 1 and 3, we have i-1>|V(G(m))|-1 or i-1<γ(G(m-2)). If i-1>|V(G(m))|-1, then i>|V(G(m))|, and by Lemma 1, 𝒟(G(m),i)=∅, a contradiction. So we have i-1<γ(G(m-2)), and since 𝒟(G(m-3),i-1)≠∅, together we have γ(G(m-3))≤i-1<γ(G(m-2)). So γ(G(m-3))+1≤i<γ(G(m-2))+1.
(⇐) If γ(G(m-3))+1≤i<γ(G(m-2))+1, then by Lemma 1, we have 𝒟(G(m-1),i-1)=𝒟(G(m-2),i-1)=∅ and 𝒟(G(m-3),i-1)≠∅.
(ii) (⇒) Since 𝒟(G(m-2),i-1)=𝒟(G(m-3),i-1)=∅, by Lemmas 1 and 3, i-1>|V(G(m))|-2 or i-1<γ(G(m-3)). If i-1<γ(G(m-3)), then i-1<γ(G(m-1)), and hence 𝒟(G(m-1),i-1)=∅, a contradiction. So we must have i-1>|V(G(m))|-2. Also since 𝒟(G(m-1),i-1)≠∅, we have i-1≤|V(G(m))|-1. Therefore we have i=|V(G(m))|.
(⇐) If i=|V(G(m))|, then by Lemma 1, we have 𝒟(G(m-2),i-1) = 𝒟(G(m-3),i-1)=∅ and 𝒟(G(m-1),i-1)≠∅.
(iii) (⇒) Since 𝒟(G(m-1),i-1)=∅, by Lemma 1, i-1>|V(G(m))|-1 or i-1<γ(G(m-1)). If i-1>|V(G(m))|-1, then i-1>|V(G(m))|-2, and by Lemma 1, 𝒟(G(m-2),i-1)=𝒟(G(m-3),i-1)=∅, a contradiction. So we must have i-1<γ(G(m-1)). But we also have i-1≥γ(G(m-2)) because 𝒟(G(m-2),i-1)≠∅. Hence, we have γ(G(m-2))+1≤i<γ(G(m-1))+1.
(⇐) If γ(G(m-2))+1≤i<γ(G(m-1))+1, then by Lemma 1, 𝒟(G(m-1),i-1)=∅, 𝒟(G(m-2),i-1)≠∅ and 𝒟(G(m-3),i-1)≠∅.
(iv)(⇒) Since 𝒟(G(m-3),i-1)=∅, by Lemma 1, we have i-1>|V(G(m))|-3 or i-1<γ(G(m-3)). Since 𝒟(G(m-2)),i-1)≠∅, by Lemma 1, we have γ(G(m-2))≤i-1≤|V(G(m))|-2. Therefore i-1<γ(G(m-3)) is not possible. Hence we must have i-1>|V(G(m))|-3. Thus i=|V(G(m))|-1 or |V(G(m))|. But i≠|V(G(m))| because 𝒟(G(m-3),i-1)=∅. So we have i=|V(G(m))|-1.
(
⇐
) If i=|V(G(m))|-1, then by Lemma 1, 𝒟(G(m-1),i-1)≠∅,𝒟(G(m-2),i-1)≠∅ and 𝒟(G(m-3),i-1)=∅.
(v)(⇒) Since 𝒟(G(m-1),i-1)≠∅,𝒟(G(m-2),i-1)≠∅, and 𝒟(G(m-3),i-1)≠∅, then by applying Lemma 1, we have γ(G(m-1))≤i-1≤|V(G(m))|-1,γ(G(m-2))≤i-1≤|V(G(m))|-2, and γ(G(m-3))≤i-1≤|V(G(m))|-3. So, by Lemma 3, γ(G(m-1))≤i-1≤|V(G(m))|-3, and hence γ(G(m-1))+1≤i≤|V(G(m))|-2.
(
⇐
) If γ(G(m-1))+1≤i≤|V(G(m))|-2, then by Lemma 1 we have the result.By Lemma6, for the construction of 𝒟(G(m),i), suffices to consider 𝒟(G(m-1),i-1),𝒟(G(m-2),i-1), and 𝒟(G(m-3),i-1). By Lemma 7, we need only to consider the five cases in the following theorem.Theorem 9.
For everyi≥γ(G(m)),(i)
if𝒟(G(m-1),i-1)=𝒟(G(m-2),i-1)=∅ and 𝒟(G(m-3),i-1)≠∅, then 𝒟(G(m),i) = {{ym-1}∪X∣X∈𝒟(G(m-3),i-1)};(ii)
if𝒟(G(m-2),i-1)=𝒟(G(m-3),i-1)=∅ and 𝒟(G(m-1),i-1)≠∅, then 𝒟(G(m),i) = 𝒟(G(m),|V(G(m))|) = {{ym}∪X∣X∈𝒟(G(m-1),i-1)};(iii)
if𝒟(G(m-1),i-1)=∅,𝒟(G(m-2),i-1)≠∅ and 𝒟(G(m-3),i-1)≠∅, then 𝒟(G(m),i) = {{ym}∪X1,{ym-1}∪X2∣X1 ∈ 𝒟(G(m-2),i-1), X2∈𝒟(G(m-3),i-1)};(iv)
if𝒟(G(m-1),i-1)≠∅,𝒟(G(m-2),i-1)≠∅ and 𝒟(G(m-3),i-1)=∅, then 𝒟(G(m),i) = {{ym}∪X1,{ym-1}∪X2∣X1 ∈ 𝒟(G(m-1),i-1), X2∈𝒟(G(m-2),i-1)};(v)
if𝒟(G(m-1),i-1)≠∅, 𝒟(G(m-2),i-1)≠∅ and 𝒟(G(m-3),i-1)≠∅ are nonempty, then 𝒟(G(m),i) = {{ym}∪X1,{ym-1}∪X2∣X1 ∈ 𝒟(G(m-1),i-1), X2∈𝒟(G(m-2),i-1)} ∪ {{ym-1}∪X∣X ∈ 𝒟(G(m-3),i-1)∖𝒟(G(m-2),i-1)} ∪ {{ym}∪X∣X∈𝒟(G(m-3), i-1)∩𝒟(G(m-2),i-1)}.Proof.
(i) Obviously{{ym-1}∪X∣X∈𝒟(G(m-3),i-1)}⊆𝒟(G(m),i). Now suppose that Y∈𝒟(G(m),i), then at least one of the vertices ym or ym-1 is in Y. If ym∈Y then by Lemma 5 at least one of the vertices ym-1,ym-2, or ym-3 is in Y. If ym-1∈Y or ym-2∈Y, then Y-{ym}∈𝒟(G(m-1),i-1), a contradiction. If ym-3∈Y, then Y-{ym}∈𝒟(G(m-2),i-1), a contradiction. Now suppose that ym-1∈Y, then by Lemma 5 at least one of the vertices ym-2,ym-3, or ym-4 is in Y. If ym-2∈Y or ym-3∈Y, then Y-{ym-1}∈𝒟(G(m-2),i-1), a contradiction. If ym-4∈Y, then Y-{ym-1}∈𝒟(G(m-3),i-1). So 𝒟(G(m),i)⊆{{ym-1}∪X∣X∈𝒟(G(m-3),i-1)}.
(ii) By Lemma8(ii), i=|V(G(m))|. If we suppose that G(m) has labeled with numbers in [|V(G(m))|], then 𝒟(G(m),i)=𝒟(G(m),|V(G)|)={[|V(G)|]}={{ym}∪X∣X∈𝒟(G(m-1),i-1)}.
(iii) It is obvious that{{ym} ∪ X1,{ym-1} ∪ X2∣X1 ∈ 𝒟(G(m-2),i-1), X2 ∈ 𝒟(G(m-3),i-1)} ⊆ 𝒟(G(m),i). Now let Y∈𝒟(G(m),i). Then ym or ym-1 is in Y. If ym∈Y, then by Lemma 5, at least one vertices ym-1,ym-2, or ym-3 is in Y. If ym-1 or ym-2 is in Y, then Y-{ym}∈𝒟(G(m-1),i-1), a contradiction, because 𝒟(G(m-1),i-1)=∅. Hence, ym-3∈Y,ym-2∉Y, and ym-1∉Y. Therefore Y=X∪{ym} for some X∈𝒟(G(m-2),i-1). Now suppose that ym-1∈Y and ym∉Y. By Lemma 5, at least one vertex labeled ym-2,ym-3, or ym-4 is in Y. By Lemma 8(iii), γ(G(m-2))≤i-1<γ(G(m-1))≤γ(G(m)), and on the other hand since 𝒟(G(m),i)≠∅, then i≥γ(G(m)). So together we have i=γ(G(m)). Therefore 𝒟(G(m),i)=Γ(G(m)), and so all these sets in Γ(G(m)) have minimum cardinality. Therefore, since Y∈𝒟(G(m),i) and ym-1∈Y, then ym-2∉Y. Hence ym-3 or ym-4 is in Y, but ym-2∉Y. Thus Y=X∪{ym-1} for some X∈𝒟(G(m-3),i-1). So 𝒟(G(m),i) ⊆ {{ym}∪X1, {ym-1}∪X2∣X1 ∈ 𝒟(G(m-2),i-1), X2∈𝒟(G(m-3),i-1)}.
(iv) By Lemma8, i=|V(G(m))|-1. If we suppose that G(m) has labeled with numbers in [|V(G(m))|], then 𝒟(G(m),i) = {[|V(G(m))|]-{x}∣x ∈ [|V(G(m))|]} = {{ym}∪X1, {ym-1}∪X2∣X1 ∈ 𝒟(G(m-1),i-1), X2∈𝒟(G(m-2),i-1)}.
(v)𝒟(G(m-1),i-1)≠∅,𝒟(G(m-2),i-1)≠∅ and 𝒟(G(m-3),i-1)≠∅. Let X∈𝒟(G(m-1),i-1), so at least one vertex labeled ym-1 or ym-2 is in X. If ym-1 or ym-2∈X, then X∪{ym}∈𝒟(G(m),i). Now let X∈𝒟(G(m-2),i-1), then ym-2 or ym-3 is in X. If ym-2 or ym-3∈X, then X∪{ym-1}∈𝒟(G(m),i). Now let X∈𝒟(G(m-3),i-1), then ym-3 or ym-4 is in X. If ym-3∈X, then X∪{x}∈𝒟(G(m),i), for x∈{ym,ym-1}. If ym-4∈X, then X∪{ym-1}∈𝒟(G(m),i). Therefore we have {{ym}∪X1, {ym-1}∪X2∣X1 ∈ 𝒟(G(m-1),i-1), X2∈𝒟(G(m-2),i-1)} ∪ {{ym-1}∪X∣X∈𝒟(G(m-3),i-1)∖𝒟(G(m-2),i-1)} ∪ {{ym}∪X∣X∈𝒟(G(m-3),i-1) ∩ 𝒟(G(m-2),i-1)} ⊆ 𝒟(G(m),i). Now, let Y∈𝒟(G(m),i), then ym∈Y or ym-1∈Y. If ym∈Y, then by Lemma 5, at least one vertex labeled ym-1,ym-2, or ym-3 is in Y. If ym-1∈Y or ym-2∈Y, then Y=X∪{ym} for some X∈𝒟(G(m-1),i-1). If ym-3∈Y,ym-2∉Y, and ym-1∉Y, then Y=X∪{ym} for some X∈𝒟(G(m-2),i-1)∩𝒟(G(m-3),i-1). Now suppose that ym-1∈Y and ym∉Y, then by Lemma 5, at least one vertex labeled ym-2,ym-3, or ym-4 is in Y. If ym-2∈Y or ym-3∈Y, then Y=X∪{ym-1} for some X∈𝒟(G(m-2),i-1). If ym-4∈Y,ym-3∉Y, and ym-2∉Y, then Y=X∪{ym-1} for some X∈𝒟(G(m-3),i-1)∖𝒟(G(m-2),i-1). So 𝒟(G(m),i) ⊆ {{ym}∪X1,{ym-1} ∪ X2∣X1∈𝒟(G(m-1),i-1), X2∈𝒟(G(m-2),i-1)} ∪ {{ym-1} ∪ X∣X ∈ 𝒟(G(m-3),i-1) ∖ 𝒟(G(m-2), i-1)} ∪ {{ym}∪X∣X ∈ 𝒟(G(m-3),i-1) ∩ 𝒟(G(m-2),i-1)}.Theorem 10.
For anym≥3 and i≥γ(G(m)),
(1)|𝒟(G(m),i)|=|𝒟(G(m-1),i-1)|+|𝒟(G(m-2),i-1)|+|𝒟(G(m-3),i-1)|.Proof.
It follows from Theorem9.Theorem 11.
For anym≥3,
(2)D(G(m),x)=x(D(G(m-1),x)+D(G(m-2),x)+D(G(m-3),x)).Proof.
We have the result by definition of domination polynomial and Theorem10.


## 3. Dominating Sets of Paths and Some Other Graphs

First we investigate the dominating sets of paths. SincePn=P1(n-1), we use the results for graph G(m) in the previous section to obtain properties of dominating sets of path. We suppose that Pn is labeled as in Figure 1(a) and denote 𝒟(Pn,i) simply by Pin.Lemma 12.
Suppose that𝒫in≠∅, then one has(i)
𝒫i-1n-1=𝒫i-1n-2=∅ and 𝒫i-1n-3≠∅ if and only if n=3k and i=k for some k∈N,(ii)
𝒫i-1n-2=𝒫i-1n-3=∅ and 𝒫i-1n-1≠∅ if and only if i=n,(iii)
𝒫i-1n-1=∅,𝒫i-1n-2≠∅, and 𝒫i-1n-3≠∅ if and only if n=3k+2 and i=⌈(3k+2)/3⌉ for some k∈N,(iv)
𝒫i-1n-1≠∅,𝒫i-1n-2≠∅, and 𝒫i-1n-3=∅ if and only if i=n-1,(v)
𝒫i-1n-1≠∅,𝒫i-1n-2≠∅, and 𝒫i-1n-3≠∅ if and only if ⌈(n-1)/3⌉+1≤i≤n-2.Proof.
(i) (⇒) By Lemmas 4 and 8(i), we have ⌈n/3⌉≤i<⌈(n-2)/3⌉+1, which give us n=3k and i=k for some k∈N.
(⇐) It follows from Lemmas 4 and 8(i).
(ii) It follows from Lemma8(ii).
(iii) (⇒) By Lemmas 4 and 8(iii), we have ⌈(n-2)/3⌉+1≤i<⌈(n-1)/3⌉+1, which give us n=3k+2 and i=k+1=⌈(3k+2)/3⌉ for some k∈N.
(⇐) It follows from Lemmas 4 and 8(iii).
(iv) It follows from Lemma8(iv).
(v) It follows from Lemmas4 and 8(v).The following theorem specify𝒫in.Theorem 13.
For everyn≥4 and i≥⌈n/3⌉,(3)𝒫in={{{2,5,…,n-4,n-1}},if𝒫i-1n-1=𝒫i-1n-2=∅,{[n]},if𝒫i-1n-2=𝒫i-1n-3=∅,{{2,5,…,n-3,n}}∪{X∪{n-1}∣X∈𝒫i-1n-3},if𝒫i-1n-1=∅,{[n]-{x}∣x∈[n]},if𝒫i-1n-3=∅,{{n}∪X1,{n-1}∪X2∣X1∈𝒫i-1n-1,X2∈𝒫i-1n-2}∪{{n-1}∪X∣X∈𝒫i-1n-3∖𝒫i-1n-2}∪{{n}∪X∣X∈𝒫i-1n-3∩𝒫i-1n-2},if𝒫i-1n-1≠∅,𝒫i-1n-2≠∅,𝒫i-1n-3≠∅.Proof.
Case
1. 𝒫i-1n-1=𝒫i-1n-2=∅ and 𝒫i-1n-3≠∅. By Lemma 12(i), n=3k and i=k for some k∈N. Therefore 𝒫in=𝒫n/3n={{2,5,…,n-4,n-1}}.
Case
2. It follows from Theorem 9(ii).
Case
3. By Theorem 9(iii), 𝒫in={{n}∪X1,{n-1}∪X2∣X1∈𝒫i-1n-2,X2∈𝒫i-1n-3}. By Lemma 12(iii), n=3k+2 and i=k+1 for some k∈N. Since 𝒫i-1n-2=𝒫k3k={{2,5,…,3k-1}}, then {X∪{3k+2}∣X∈𝒫k3k}={{2,5,…,3k-1,3k+2}}. Therefore 𝒫in={{2,5,…,n-3,n}} ∪ {X∪{n-1}∣X∈𝒫i-1n-3}.
Cases 4 and 5 follow from Theorem9(iv) and (v), respectively.Example 14.
We use Theorem13 to construct 𝒫i6 for 2≤i≤6. Since 𝒫15=𝒫14=∅ and 𝒫13={{2}}, by Theorem 13, 𝒫26={{2,5}}. Since 𝒫55={[5]},𝒫54=∅, and 𝒫53=∅, we get 𝒫66={[6]}. Since 𝒫45={{1,2,3,4}, {1,2,3,5}, {1,3,4,5}, {2,3,4,5}, {1,2,4,5}}, 𝒫44={[4]}, and 𝒫43=∅, then by Theorem 13, 𝒫56={[6]-{x}∣x∈[6]}={{1,2,3,4,6}, {1,2,3,5,6}, {1,3,4,5,6}, {2,3,4,5,6}, {1,2,4,5,6}, {1,2,3,4,5}}. And, for construction 𝒫36={{1,3,5}, {1,3,6}, {2,3,6}, {2,3,5}, {1,4,6}, {1,4,5}, {2,5,6}, {2,4,6}, {2,4,5}, {1,2,5}}, by Theorem 13, 𝒫36={X1∪{6}, X2∪{5}∣X1∈𝒫25, X2∈𝒫24}∪{{1,2}∪{5}, {1,3}∪{6}, {2,3}∪{6}}. Finally, since 𝒫35={{1,3,5}, {1,2,4}, {2,4,5}, {2,3,4}, {2,3,5}, {1,4,5}, {1,3,4}, {1,2,5}}, 𝒫34={{1,2,3}, {1,2,4}, {2,3,4}, {1,3,4}}, and 𝒫33={[3]}, then 𝒫46={X1∪{6},X2∪{5}∣X1∈𝒫35, X2∈𝒫34}∪{X∪{6}∣X∈𝒫33}={{1,2,3,5}, {1,2,3,6}, {1,2,4,6}, {1,3,5,6}, {1,3,4,6}, {1,3,4,5}, {1,2,5,6}, {1,2,4,5}, {2,3,4,6}, {1,4,5,6}, {2,3,4,5}, {2,4,5,6}, {2,3,5,6}}.Theorem 15.
If𝒫in is the family of dominating set of Pn with cardinality i, then |𝒫in|=|𝒫i-1n-1|+|𝒫i-1n-2|+|𝒫i-1n-3|.Proof.
It follows from Theorem10.Remark 16.
We have obtained [12, Lemma 12 and Theorem  5] with a different approach.As other examples of graphG(m), we study the dominating sets of some other graphs. By Theorem 10, the recursive formula in this theorem is true for every graphs which contain a gluing path with at least 3 vertices. Also, if we have the domination number of graphs, then we can study the properties of their dominating sets by Theorem 9 and Lemma 8. Here, we consider a special case of graph Pn(m) which is a tree. We denote this tree by Tn(m). In other words Tn(m) is a tree, such that Tn(0)=Pn, and for m≥1, Tn(m)=(A,B,E) where A∪B is its vertex set, A={a1,…,an},B={b1,…,bm}, and the edge set E={aiai+1:1≤i≤n-1}∪{bibi+1:1≤i≤m-1}∪{an-1b1}; see Figure 2. For obtaining the domination number of Tn(m), we need the following lemma which follows from observation.Figure 2
The treeTn(m).Lemma 17.
For everyn≥0 and m≥3, γ(Tn(m))=γ(Tm-2(n+2)).Theorem 18.
For everyn≥3 and m≥0, γ(Tn(m))=⌈n/3⌉+⌈(m-1)/3⌉.Proof.
By induction onm. If m=0, then γ(Tn(0))=γ(Pn)=⌈n/3⌉. Now suppose that the theorem is true for all numbers less than or equal m-1, and we prove it for m. By applying Theorem 2 for e=an-1b1, we have the following inequalities:
(4)⌈n3⌉+⌈m3⌉-1≤γ(Tn(m))≤⌈n3⌉+⌈m3⌉.
Similarly by applying Theorem 2 for e=b2b3,bm-3bm-2 and induction hypothesis, we have the following inequalities; respectively,
(5)⌈n3⌉+⌈m-23⌉≤γ(Tn(m))≤⌈n3⌉+⌈m-23⌉+1,(6)⌈n3⌉+⌈m-43⌉≤γ(Tn(m))≤⌈n3⌉+⌈m-43⌉+1.
Now if m=3k for some k∈N, then by (4) and (5) we have γ(Tn(m)) = ⌈n/3⌉+k = ⌈n/3⌉ + ⌈(m-1)/3⌉.
Ifm=3k+1 for some k∈N, then by (4) and (6) we have γ(Tn(m))=⌈n/3⌉+k=⌈n/3⌉+⌈(m-1)/3⌉.
Now ifm=3k+2 for some k∈N, we will consider the following cases.(i)
One hasn=3k′ for some k′∈N. By applying Theorem 2 for an-1an, we have the following inequalities:
(7)⌈n+m-13⌉≤γ(Tn(m))≤⌈n+m-13⌉+1.Now, by (4) and (7), we have γ(T3k′(3k+2))=k+k′+1=⌈n/3⌉+⌈(m-1)/3⌉.(ii)
One hasn=3k′+2 for some k′∈N. By Theorem 2 for e=a1a2 we have
(8)⌈n-13⌉+⌈m-13⌉≤γ(Tn(m))≤⌈n-13⌉+⌈m-13⌉+1.By (4) and (8), we have γ(T3k′+2(3k+2))=k+k′+2=⌈n/3⌉+⌈(m-1)/3⌉.(iii)
One hasn=3k′+1 for some k′∈N. We will prove that γ(T3k′+1(3k+2))=k+k′+2. We do it by induction on k. If k=0, then by Lemma 17, γ(T3k′+1(2))=γ(T4(3k′-1))=2+k′. So the result is true for k=0. Now suppose that the result is true for all number less than k, and we prove it for k. By Lemma 17 and the induction hypothesis, we have the following equalities for k′-1<k:
(9)γ(T3k′+1(3k+2))=γ(T3k+4(3k′-1))=γ(T3(k+1)+1(3(k′-1)+2))=k′-1+k+1+2=k′+k+2.Ifk′-1>k, then for some t>0, k′=k+1+t. Again by Lemma 17,
(10)γ(T3k′+1(3k+2))=γ(T3k+3t+4(3k+2))=γ(T3k+4(3(k+t)+2))=k+t+k+1+2=k′+k+2.Finally, fork′-1=k, we have γ(T3k′+1(3k+2)) = γ(T3k+4(3k+2)) = γ(T3(k+1)+1(3k+2) = 2k + 3 = k + k′ + 2. Therefore in all cases γ(Tn(m))=⌈n/3⌉+⌈(m-1)/3⌉.Let𝒟(Tn(m),i) or simply 𝒟in,m be the family of dominating set of Tn(m) with cardinality i. By Lemma 8 and Theorem 9 we prove the following lemma, which is some properties of 𝒟in,m.Lemma 19.
Suppose that𝒟in,m≠∅, then(i)
𝒟i-1n,m-1=𝒟i-1n,m-2=∅ and 𝒟i-1n,m-3≠∅ if and only if m=3k+1, i=⌈n/3⌉+k, for some k∈N,(ii)
𝒟i-1n,m-2=𝒟i-1n,m-3=∅, and 𝒟i-1n,m-1≠∅ if and only if i=n+m,(iii)
𝒟i-1n,m-1=∅,𝒟i-1n,m-2≠∅, and 𝒟i-1n,m-3≠∅ if and only if m=3k, i=⌈n/3⌉+k, for some k∈N,(iv)
𝒟i-1n,m-1≠∅,𝒟i-1n,m-2≠∅, and 𝒟i-1n,m-3=∅, if and only if i=m+n-1,(v)
𝒟i-1n,m-1≠∅,𝒟i-1n,m-2≠∅ and 𝒟i-1n,m-3≠∅ if and only if ⌈n/3⌉+⌈(m-2)/3⌉+1≤i≤m+n-2.Proof.
(i) By Lemma8(i) and Theorem 18, ⌈n/3⌉+⌈(m-4)/3⌉+1≤i<⌈n/3⌉+⌈(m-3)/3⌉+1, which give us m=3k+1,i=⌈n/3⌉+k, for some k∈N.
(ii) By Lemma8(ii), i=|V(Tn(m))|=m+n.
(iii) By Lemma8(iii) and Theorem 18, ⌈n/3⌉+⌈(m-3)/3⌉+1≤i<⌈n/3⌉+⌈(m-2)/3⌉+1. Therefore m=3k and i=⌈n/3⌉+k for some k∈N.
(iv) By Lemma8(iv), i=|V(Tn(m))|-1=n+m-1.
(v) By Lemma8(v) and Theorem 18, ⌈n/3⌉+⌈(m-2)/3⌉+1≤i≤m+n-2.Here, we suppose that the treeTn(m) labeled as shown in Figure 3. The following theorem constructs 𝒟in,m from 𝒟i-1n,m-1,𝒟i-1n,m-2, and 𝒟i-1n,m-3.Figure 3
LabeledTn(m).Theorem 20.
(i) If𝒟i-1n,m-1=𝒟i-1n,m-2=∅ and 𝒟i-1n,m-3≠∅, then
(11)𝒟in,m={{m+n-1}∪X∣X∈𝒟i-1n,m-3}.
(ii) If𝒟i-1n,m-2=𝒟i-1n,m-3=∅ and 𝒟i-1n,m-1≠∅, then
(12)𝒟in={{m+n}∪X∣X∈𝒟i-1n,m-1}={[m+n]}.
(iii) If𝒟i-1n,m-1=∅,𝒟i-1n,m-2≠∅, and 𝒟i-1n,m-3≠∅, then
(13)𝒟in,m={{{m+n-1}∪X2∣X1∈𝒟i-1n,m-2,X2∈𝒟i-1n,m-3}{m+n}∪X1,{m+n-1}∪X2∣X1∈𝒟i-1n,m-2,X2∈𝒟i-1n,m-3}.
(iv) If𝒟i-1n,m-3=∅,𝒟i-1n,m-2≠∅, and 𝒟i-1n,m-1≠∅, then
(14)𝒟in={{{m+n-1}∪X2X1∈𝒟i-1n,m-1,X2∈𝒟i-1n,m-2}{m+n}∪X1,{m+n-1}∪X2∣X1∈𝒟i-1n,m-1,X2∈𝒟i-1n,m-2}.
(v) If𝒟i-1n,m-1,𝒟i-1n,m-2, and 𝒟i-1n,m-3 are nonempty, then
(15)𝒟in,m={{m+n}∪X1,{m+n-1}∪X2∣X1∈𝒟i-1n,m-1,X2∈𝒟i-1n,m-2}∪{{m+n-1}∪X∣X∈𝒟i-1n,m-3∖𝒟i-1n,m-2}∪{{m+n}∪X∣X∈𝒟i-1n,m-3∩𝒟i-1n,m-2}.Proof.
It follows from Theorem9.Now we obtain the following theorem from Theorem20 or Theorem 10.Theorem 21.
If𝒟in,m is the family of dominating set of Tn(m) with cardinality i, then |𝒟in,m|=|𝒟i-1n,m-1|+|𝒟i-1n,m-2|+|𝒟i-1n,m-3|.Note that the treeTn(m) is obtained by gluing an end vertex of a path Pm to the vertex an-1 of Pn. We now consider another type of related tree Tm,n(k) (or special case of (Tn(m))(k)), which is obtained from Tn(m) by gluing an end vertex of a path Pk to the vertex a2 of Pn, see Figure 4. In other words, let Tm,n(k)=(A,B,C,E), k,n≥0, where A∪B∪C is its vertex set, A={a1,…,an}, B={b1,…,bm}, C={c1,…,ck}, and the edge set E = {aiai+1:1≤i≤n-1} ∪ {bibi+1:1≤i≤m-1} ∪ {cici+1:1≤i≤k-1} ∪ {an-1b1,a2c1}.The graphsTm,n(k) and Cn(m), respectively.
(a)
(b)Theorem 22.
For everyn≥3 and m,k≥0, γ(Tm,n(k))=⌈n/3⌉+⌈(m-1)/3⌉+⌈(k-1)/3⌉.Proof.
Similar to the proof of Theorem18.By Theorem10, we have the following theorem.Theorem 23.
If𝒟in,m,k is the family of dominating set of Tm,n(k) with cardinality i, then |𝒟in,m,k| = |𝒟i-1n,m,k-1| + |𝒟i-1n,m,k-2| + |𝒟i-1n,m,k-3|.As other examples for graphsG(m), we consider graph Cn(m) which obtain by gluing a path to one vertex of cycle as shown in Figure 4.  By Theorem 10 we have the following theorem for Cn(m).Theorem 24.
For everyn,m≥3, |𝒟(Cn(m),i)| = |𝒟(Cn(m-1),i-1)| + |𝒟(Cn(m-2),i-1)| + |𝒟(Cn(m-3),i-1)|.Let sun be a graph which is obtained by gluing end vertices of pathsPi1,Pi2,…,Pin to the n vertices of Cn. We denote this graph by S(i1,i2,…,in). Since sun is the special case of (⋯((Cn(i1))(i2))⋯(in), we have the following theorem for sun.Theorem 25.
Suppose that for every1≤j≤n, ij≥3 and i≥γ(S(i1,i2,…,in)), then |𝒟(S(i1,i2,…,in),i)|=|𝒟(S(i1,i2,…,in-1),i-1)| + |𝒟(S(i1,i2,…,in-2),i-1)| + |𝒟(S(i1,i2,…,in-3),i-1)|.



---

*Source: 587196-2013-03-20.xml*