ABSTRACT

Let G = (V, E) 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. Let be the square of the Path and let denote the family of all dominating sets of with cardinality i. Let. In this paper, we obtain a recursive formula for. Using this recursive formula, we construct the polynomial, , which we call domination polynomial of and obtain some properties of this polynomial.

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 Ifthen. 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 and1) 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 X₁. If n – 1, n – 2 or n – 3 ÎX_1, then

.

Let, then n – 2 or n – 3 or n – 4 is inX₂.

If n – 2, n – 3 or n – 4 Î X_2, then

.

Now let then n – 3, n – 4 or n – 5 is in X₃. If n – 3 or n – 4 or n – 5 Î X₃, then

.

Now let, then n – 4, or n – 5 or n – 6 is in X₄.

If n – 4 Î X₄, then. If n – 5 Î X₄, then

.

If n – 6 Î X₄, 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 S₁

= 1, S₂ = 3, S₃ = 7, S₄ = 13 and S₅ = 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.

REFERENCES