1. Introduction
Let G = (V, E) be a simple graph of order |V| = n. For any vertex v Î V, the open neighbourhood of n is the set 
and the closed neighbourhood of n is the set
. For a set S Í V, the open neighbourhood of S is 
and the closed neighbourhood of S is
. A set S
Í V is a dominating set of G, if N[S] = V, or equivalently, every vertex in V-S is adjacent to at least one vertex in S. The domination number of a graph G is defined as the minimum size of a dominating set of vertices in G and it is denoted as
. A simple path is a path in which all its internal vertices have degree two, and the end vertices have degree one and is denoted by
.
Definition 1.1.: Let 
be the family of dominating sets of a graph G with Cardinality i and let
.
Then the domination polynomial 
of G is defined as
.
where 
is the domination number of G.
Result 1.2. [1]: If a graph G consists of m components
, then
.
Result 1.3. [1]: Let 
and 
be graphs of order 
and 
respectively. Then
Result 1.4. [1]: Let G be a bipartite graph with bipartition (X,Y). Then G contains a matching that saturates every vertex in X if and only if for all S Í V
.
Result 1.5. [1]: Let G be a graph of order n. Then for every
, we have
.
Result 1.6. [1]: For any graph G of order n,
.
Result 1.7. [1]: For any graph G of order n and
, we have
.
Hence
.
Definition 1.8: The Square of a graph with the same set of vertices as G and an edge between two vertices if and only if there is a path of length at most 2 between them. The second power of a graph is also called its Square.
Let 
be the square of the path
(2nd power )with n vertices. Let 
be the family of dominating sets of the graph
with cardinality i and let
.
We call the polynomial
the domination polynomial of the graph
[2].
In the next section, we construct the families of the dominating sets of the square of paths by recursive method.
As usual we use 
for the largest integer less than or equal to x and 
for the smallest integer greater than or equal to x. Also, we denote the set 
by [n], throughout this paper.
2. Main Result
Let 
be the family of dominating sets of 
with cardinality i. We investigate the dominating sets of
. We need the following lemma to prove our main results in this section.
Lemma 2.1. [3]: 
By Lemma 2.1 and the definition of domination number, one has the following Lemma:
Lemma 2.2. 
if and only if 
or
. A simple path is a path in which all its internal vertices have degree two, and the end vertices have degree one. The following Lemma follows from observation [2].
Lemma 2.3. [2]: If a graph G contains a simple path of length 5k – 1, then every dominating set of G must contain at least k vertices of the path.
In order to find a dominating set of
, with cardinality i, we only need to consider
, 
,
, 
and
. The families of these dominating sets can be empty or otherwise. Thus, we have eight combinations, whether these five families are empty or not. Two of these combinations are not possible (Lemma 2.5(i), & (ii)). Also, the combination that
does not need to be considered because it implies that 
(See Lemma 2.5 (iii)). Thus we only need to consider five combinations or cases. We consider those cases in Theorem 2.7.
Lemma 2.4.: If
, and there exists x
Î [n] such that
, then
.
Proof: Suppose that
. Since
Y contains at least one vertex labeled n – 6, n – 7 or n – 8.
If
, then
, a contradiction. Hence n – 7 or n – 8 Î Y, but then in this case, 
, for any xÎ [n], also a contradiction.
Lemma 2.5.:
1) If
then
2) If
, 
then
3) If
, 
,
, 
,
, then 
Proof:
1) Since
, by Lemma 2.2, 
(or)
. In either case, we have 
.
2) Suppose that
, so by Lemma 2.2we have 
or 
If
then
. Therefore
, a contradiction.
3) Suppose that
, Let
. Thus, at least one vertex labeled n or n – 1 or n – 2 is in Y. If n Î Y, then by Lemma (2.3), at least one vertex labeled n – 1, n – 2, n – 3, n – 4 or n – 5 is in Y. If n – 1 Î Y or n – 2 Î Y, then
, a contradiction.
If n – 3 Î Y, then
, a contradiction. Now, suppose that n – 1 Î Y. Then, by Lemma 2.3, at least one vertex labeled n – 2, n – 3, n – 4, n – 5 or n – 6 is in Y. If n – 2 Î Y or n – 3 Î Y, then
a contradiction. If n – 4 Î Ythen
, a contradiction.
If n – 5 Î Y, then
, a contradiction If n – 6 Î Y, then
, a contradiction. Therefore,
.
Lemma 2.6.: If
, then 1) 
and 
if and only if n = 5k and i = k for some k Î N;
2) 
then 
if and only if i = n;
3)
, 
,
, 
,
, if and only if n = 5k + 2 and
for some kÎN;
4)
, 
,
, 
, and
if and only if i = n – 3.
5)
, 
,
, 
, and
if and only if
.
wang#title3_4:spwang#title3_4:spwang#title3_4:spwang#title3_4:spProof:
1) (Þ)
Since
by Lemma 2.2,
or 
If
, then 
and by Lemma 2.2, 
, a contradiction.
So
, and since
, we have
, which implies that n = 5k and i = k for some kÎN.
(Ü) If n = 5k and i = k for some kÎN, then by Lemma 2.2,
and
.
2) (Þ) Since
by Lemma 2.2,
or
.
If
, then 
and hence
, a contradiction.
So
. Also,
.
Therefore
. Therefore
. But
. Hence i = n.
(Ü) If i = n, then by lemma 2.2,
then
.
3) (Þ) Since
, by Lemma 2.2,
or
.
If
, then
, by Lemma 2.2,
a contradiction.
Therefore
.
But
, because
.
Therefore
.
Hence,
.
This holds only if n = 5k + 2 and
for some k Î N.
(Ü) If n = 5k + 2 and 
for some k Î N, then by Lemma 2.2,
, 
,
, 
and
.
4) (Þ) Since
, by Lemma 2.2,
or
.
Since
, by Lemma 2.2,
.
Therefore 
is not possible. Therefore
. Therefore
.
Therefore
.
Since
,
.
Therefore
. Hence
.
(Ü) if 
then By Lemma 2.2,
, 
,
, 
and
.
5) (Þ) Since
, 
, and
, then by applying Lemma (2.2),
, 
,
, 
and
.
So
and hence
.
(Ü) If
, then the result follows from Lemma 2.2.
Theorem 2.7.: For every 
and
1) If
and
then
.
2) If
and
then
.
3) If
, 
,
, 
and
then
(2.1)
4) If
, 
,
then
.
5) If
, 
,
, 
, 
then
(2.2)
wang#title3_4:spwang#title3_4:spwang#title3_4:spwang#title3_4:spProof:
1) Since
and 
by Lemma 2.6 i) n = 5k, and i = k for some k Î N.
Clearly the set 
has 
elements.
By the definition of
, 3 has joining with 1, 2, 4, 5, and 8 has joining with 6, 7, 9, 10. Therefore 3 and 8 covers all the vertices up to10for n = 10. Proceeding like this, we obtain that 
covers all Vertices up to n. The other sets with cardinality 
are
, 
etc. In the first set, 
does not cover the vertex n. The second set does not cover the vertex 1and so on.
Therefore 
is the only dominating set of cardinality
.
2) We have
and
.
By Lemma 2.6 (ii), we have i = n. So,
.
3) We have
, 
,
, 
and
.
By Lemma 2.6 (iii), n = 5k + 2 and
for some k Î N.
Since
,
.
Also, if 
then
Therefore, we have
(2.3)
Now let
. Then 5k + 2, or 5k + 1 is in Y. If 5k + 2 ÎY, then by Lemma 3, at least one vertex labeled 5k + 1, 5k or 5k – 1 is in Y. If 5k + 1 or 5k is in Y, then
a contradiction; because
.
Hence 5k – 1 Î Y, 5k Ï Y and 5k + 1 Ï Y.
Therefore, 
for some
;
that is
. Now suppose that 5k + 1 ÎY and 5k + 2 Ï Y. By Lemma 2.3 at least one vertex labeled 5k, 5k – 1 or 5k – 2 is in Y. If 5k Î Y then
a contradiction because 5k Ï X for all
.
Therefore 5k – 1, or 5k – 2 is in Y, but 5kÏY.
Thus 
for some
. So
(2.4)
From (2.3) and (2.4),
4) If
,
,
by Lemma 2.6 (iv) i = n – 1.
Therefore
.
5)
, 
,
, 
,
.
Let
, so at least one vertex labeled n – 1, n – 2 or n – 3 is in X1. If n – 1, n – 2 or n – 3 ÎX1, then
.
Let
, then n – 2 or n – 3 or n – 4 is inX2.
If n – 2, n – 3 or n – 4 Î X2, then
.
Now let 
then n – 3, n – 4 or n – 5 is in X3. If n – 3 or n – 4 or n – 5 Î X3, then
.
Now let
, then n – 4, or n – 5 or n – 6 is in X4.
If n – 4 Î X4, then
. If n – 5 Î X4, then
.
If n – 6 Î X4, then
. Thus we have
(2.5)
Now suppose that n – 1Î Y, n Î Y then by Lemma 2.3, at least one vertex labeled n – 2, n – 3 or in Y. If n – 2 Î Y then 
for some
, 
.
Now suppose that, n – 5 ÎY & n – 4 Î Y, then by Lemma 2.3 one vertex labeled n – 6, n – 7, in Y.
If n – 4 Î Y, then 
for
, 
So
(2.6)
From (2.5) & (2.6)
3. Domination polynomial of 
Let 
be the domination polynomial of a path
. In this section, we derive the expression for
.
Theorem 3.1.
a) If 
is the family of dominating sets with cardinality i of
, then
where
.
b) For every
,
with the initial values
, 
,
,
,
.
wang#title3_4:spwang#title3_4:spwang#title3_4:spwang#title3_4:spProof:
a) Using (i), (ii), (iii), (iv) and (v) of Theorem 2.7, we prove (a) part.
1) Suppose (i) of Theorem 2.7 holds.
From (v), we have
.
Since
,
Therefore
.
Therefore
.
Therefore, in this case 
holds.
2) Suppose (ii) of Theorem 2.7 holds.
From (v), we have
.
Since 
Therefore 
Therefore
.
Therefore, In this case 
holds.
3) Suppose (iii) of Theorem 2.7 holds.
From (v), we have
.
Since
,
.
Therefore
.
Therefore
.
4) Suppose (v) of Theorem 2.7 holds.
From (v), we have
Therefore
.
Therefore
.
Therefore, we have the theorem.
b)
with the initial values
,
,
.
We obtain 
for 1 ≤ n ≤ 10 as shown in Table 1.
Table 1.
, the number of dominating set of
with cardinality i.
In the following Theorem, we obtain some properties of 
Theorem 3.2. The following properties hold for the coefficients of
;
1) 
for every n Î N.
2) 
for every n Î N 3) 
for every 
4) 
for every 
5) 
for every 
6) 
for every 
7) 
for every n Î N.
wang#title3_4:spwang#title3_4:spwang#title3_4:spwang#title3_4:spProof:
1) Since
, we have 
.
2) Since
, we have the result 3) Since
, we have
.
4) By induction on n. The result is true for n = 3.
(from table)
Therefore, the result is true for n = 4.
Now suppose that the result is true for all numbers less than “n” and we prove it for n.
By Theorem 3.1,
5) By induction on n. The result is true for n = 4.
(from table)
Therefore the result is true for n = 1. Now suppose the result is for all natural numbers less than n.
By Theorem 3.1,
6) By induction on n. Let n = 5
(from table)
Therefore the result is true for n =1.
Now suppose that the result is true for all natural numbers less than or equal to n.
7) From the table it is true.
Theorem 3.3.
1) 
2) For every
,
3) If
, then for every n ≥ 6,
with initial values S1
= 1, S2 = 3, S3 = 7, S4 = 13 and S5 = 25.
wang#title3_4:spwang#title3_4:spwang#title3_4:spwang#title3_4:spProof:
1) Proof by induction on n First suppose that n = 2 then,
We have the result.
2) By Theorem 3.1, We have
Therefore we have the result 3) By theorem (3.1), we have
.
4. Conclusions
In [2], the domination polynomial of path was studied and obtained the very important property,
.
It is interesting that we have derived an analogues relation for the square of path of the form
One can characterise the roots of the polynomial 
and identify whether they are real or complex. Another interesting character r to be investigated is whether 
is log concave are not.