# On the Domination Polynomial of Some Graph Operations

Authors: Saeid Alikhani
Journal: ISRN Combinatorics
 (2013)

---

## Abstract

LetG be a simple graph of order n. The domination polynomial of G is the polynomial D(G,λ)=∑i=0n‍d(G,i)λi, where d(G,i) is the number of dominating sets of G of size i. Every root of D(G,λ) is called the domination root of G. In this paper, we study the domination polynomial of some graph operations.


---

## Body

## 1. Introduction

LetG be a simple graph. For any vertex v∈V, the open neighborhood of v is the set N(v)={u∈V∣uv∈E} and the closed neighborhood is the set N[v]=N(v)∪{v}. For a set S⊆V, the open neighborhood of S is N(S)=⋃v∈S‍N(v) and the closed neighborhood of S 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. An i-subset of V(G) is a subset of V(G) of cardinality i. Let 𝒟(G,i) be the family of dominating sets of G which are i-subsets and let d(G,i)=|𝒟(G,i)|. The polynomial D(G,x)=∑i=0|V(G)|‍d(G,i)xi is defined as domination polynomial of G [1]. This polynomial has been introduced by the author in his Ph.D. thesis in 2009 [2]. A root of D(G,x) is called a domination root of G. More recently, domination polynomial has found application in network reliability [3]. For more information and motivation of domination polynomial and domination roots refer to [1, 2].The joinG=G1+G2 of two graphs G1 and G2 with disjoint vertex sets V1 and V2 and edge sets E1 and E2 is the graph union G1∪G2 together with all the edges joining V1 and V2. The corona of two graphs G1 and G2, is the graph G=G1∘G2 formed from one copy of G1 and |V(G1)| copies of G2, where the ith vertex of G1 is adjacent to every vertex in the ith copy of G2 [4]. the Cartesian product of two graphs G and H is denoted by G□H, is the graph with vertex set V(G)∪V(H) and edges between two vertices (u1,v1) and (u2,v2) if and only if either u1=u2 and v1v2∈E(H) or u1u2∈E(G) and v1=v2.In this paper, we study the domination polynomials of some graph operations.


## 2. Main Results

As is the case with other graph polynomials, such as chromatic polynomials and independence polynomials, it is natural to consider the domination polynomial of composition of two graphs. It is not hard to see that the formula for domination polynomial of join of two graphs is obtained as follows.Theorem 1 (see [1]).
LetG1 and G2 be graphs of orders n1 and n2, respectively. Then
(1)D(G1+G2,x)=((1+x)n1-1)((1+x)n2-1)+D(G1,x)+D(G2,x).It is obvious that this operation of graphs is commutative. Using this product, one is able to construct a connected graphG with the number of dominating sets n, where n is an arbitrary odd natural number; see [5].Let to consider the corona of two graphs. The following theorem gives us the domination polynomial of graphs of the formH∘K1 which is the first result for domination polynomial of specific corona of two graphs.Theorem 2 (see [1]).
LetG be a graph. Then D(G,x)=xn(x+2)n if and only if G=H∘K1 for some graph H of order n.It is easy to see that the corona operation of two graphs does not have the commutative property. The following theorem gives us the domination polynomial ofK1∘H.Theorem 3.
For every graphH of order m, D(K1∘H,x)=x(1+x)m+D(H,x).Proof.
In each graph of the formK1∘H, we have two cases for a dominating set S.
Case  1.
S includes u (the vertex originally in K1) and an arbitrary subset of the m vertices from the copy of H. The generating function for the number of dominating sets of graph in this case is x(1+x)m.
Case  2.
S does not include u and it is exactly a dominating set of H. In this case D(H,x) is the generating function.
By addition principle, we haveD(K1∘H,x)=x(1+x)m+D(H,x).The following theorem gives a formula for domination polynomial of corona products of two graphs.Theorem 4.
LetG=(V,E) and H=(W,F) be nonempty graphs of order n and m, respectively. Then
(2)D(G∘H,x)=(x(1+x)m+D(H,x))n.Proof.
By Theorem3, it suffices to prove that D(G∘H,x)=(D(K1∘H,x))n. In the corona of two graphs G and H, every vertex u∈V of G is adjacent to all vertices of the corresponding copy of H. So, we can delete all edges in E in the corona. Therefore, the arising graph is the disjoint union of |V| copies of the corona K1∘H. Therefore, D(G∘H,x)=(D(K1∘H,x))n.As a consequence of the above theorem, we have the following corollary.Corollary 5.
(i) LetG be a connected graph of order n. Then, G=H∘K¯2, for some graph H, if and only if D(G,x)=x(n/3)(x2+3x+1)(n/3) (see [1]) .
(ii) LetH be a graph of order n and G=H∘Km¯. Then D(G,x)=(x(1+x)m+xm)n.It is interesting that for the classification of graphs with exactly two, three, and four domination roots, we must consider some kinds of corona of two graphs. For more information, see [1].To study more we need the following theorem.Theorem 6 (see [2]).
IfG  has  t connected components G1,…,Gt, then D(G,x)=∏i=1t‍D(Gi,x).Now we will consider the Cartesian product of two graphs. First we prove the following easy result.Theorem 7.
IfG  has  t  connected components G1,…,Gt, then
(3)D(G□H,x)=∏i=1t‍D(Gi□H,x).Proof.
Since we have⋃i=1t‍Gi□H=⋃i=1t‍(Gi□H), we have the result by Theorem 6.Despite the above property, it is difficult to determine the domination polynomial of this product, even in such simple cases as the grid graphsPn□Pm.Now we consider another operation of two graphs. LetG and H be graphs, with V(G)={v1,…,vn}. The graph G⋄H formed by substituting a copy of H for every vertex of G is formally defined by taking a disjoint copy of H, Hv, for every vertex v of G and joining every vertex in Hu to every vertex in Hv if and only if u is adjacent to v in G.The following result is also proven in [6, Lemma 3].Theorem 8.
For any graphG, D(G⋄Kt,x)=D(G,(1+x)t-1).Proof.
Note that the closed neighborhood of the vertex(u,v) of graph G⋄Kt is (NG[u],Kt). To make a dominating set of G⋄Kt, suppose that S⊂V(G) is a dominating set for G. It is easy to see that ⋃s∈S‍{(s,v)∣v∈As} is a dominating set of G⋄Kt, where {As∣s∈S} is a family of arbitrary nonempty subsets of V(Kt). Therefore, every v∈S corresponds to all nonempty subsets of G⋄Kt which have the generating function (1+x)t-1. So we have the result.We would like to obtain some corollaries. We recall the following theorems.Theorem 9 (see [7]).
(i) For everyn≥4,
(4)D(Pn,x)=x[D(Pn-1,x)m+D(Pn-2,x)+D(Pn-3,x)],
with the initial values D(P1,x)=x,D(P2,x)=x2+2x,D(P3,x)=x3+3x2+x.
(ii) For everyn≥4,
(5)D(Cn,x)=x[D(Cn-1,x)m+D(Cn-2,x)+D(Cn-3,x)],
with the initial values D(C1,x)=x,D(C2,x)=x2+2x,D(C3,x)=x3+3x2+3x.Here we consider the graphs obtained by selecting one vertex in each ofn triangles and identifying them. Some call them Dutch Windmill graphs [8, 9] and friendship graphs.Theorem 10.
For everyn∈ℕ,
(6)D(G3n,x)=(2x+x2)n+x(1+x)2n.Proof.
It is easy to see thatG3n is join of K1 and nK2. Now by Theorem 1, we have
(7)D(G3n,x)=D(K1,x)+D(nK2,x)+((1+x)2n-1)x=(2x+x2)n+x(1+x)2n.Theorem8 can be used to generalize recurrence relations for the domination polynomial of some families of graphs. For example, we state and prove the following theorem.Theorem 11.
(i) Suppose thatGn,t=Pn⋄Kt. Then
(8)D(Gn,t,x)=((x+1)t-1)×[D(Gn-1,t,x)+D(Gn-2,t,x)mm+D(Gn-3,t,x)].
(ii) Suppose thatHn,t=Cn⋄Kt. Then
(9)D(Hn,t,x)=((x+1)t-1)×[D(Hn-1,t,x)+D(Hn-2,t,x)mm+D(Hn-3,t,x)].
(iii)(10)D(G3n⋄Kt,x)=((1+x)2t-1)n+((1+x)t-1)(1+x)2nt.Proof.
(i) From Theorem8, we have D(Gn,t,x)=D(Pn,(1+x)t-1). Now by Part (i) of Theorem 9, we have the result.
(ii) From Theorem8, we have D(Hn,t,x)=D(Cn,(1+x)t-1). Now by Part (ii) of Theorem 9, we have the result.
(iii) From Theorem8, we have D(G3n⋄Kt,x)=D(G3n,(1+x)t-1). Now by Theorem 10, we have the result.


## 3. Conclusion

In this paper, we studied the domination polynomials of some graph operations. There are some open problems which are interesting to consider.(i) What is the basic formula for the domination polynomial of the Cartesian product of two graphs?For two graphsG and H, let G[H] be the graph with vertex set V(G)×V(H) and such that vertex (a,x) is adjacent to vertex (b,y) if and only if a is adjacent to b (in G) or a=b and x is adjacent to y (in H). The graph G[H] is the lexicographic product (or composition) of G and H and can be thought of as the graph arising from G and H by substituting a copy of H for every vertex of G. There is a main problem.(ii) How can compute the domination polynomial of Lexicographic product of the two graphs?



---

*Source: 146595-2013-08-27.xml*