On the Domination Polynomial of Some Graph Operations

Let be a simple graph of order . The domination polynomial of is the polynomial , where is the number of dominating sets of of size . Every root of is called the domination root of . In this paper, we study the domination polynomial of some graph operations. 1. Introduction Let be a simple graph. For any vertex , the open neighborhood of is the set and the closed neighborhood is the set . For a set , the open neighborhood of is and the closed neighborhood of is . A set is a dominating set if , or equivalently, every vertex in is adjacent to at least one vertex in . An -subset of is a subset of of cardinality . Let be the family of dominating sets of which are -subsets and let . The polynomial is defined as domination polynomial of [1]. This polynomial has been introduced by the author in his Ph.D. thesis in 2009 [2]. A root of is called a domination root of . 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 join of two graphs and with disjoint vertex sets and and edge sets and is the graph union together with all the edges joining and . The corona of two graphs and , is the graph formed from one copy of and copies of , where the th vertex of is adjacent to every vertex in the th copy of [4]. the Cartesian product of two graphs and is denoted by , is the graph with vertex set and edges between two vertices and if and only if either and or and . 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]). Let and be graphs of orders and , respectively. Then It is obvious that this operation of graphs is commutative. Using this product, one is able to construct a connected graph with the number of dominating sets , where 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 form which is the first result for domination polynomial of specific corona of two graphs. Theorem 2 (see [1]). Let be a graph. Then if and only if for some graph of order . It is easy to see that the corona operation of two graphs does not have the commutative property. The following theorem gives