Construction of Dominating Sets of Certain Graphs

Let be a simple graph. A set is a dominating set of , if every vertex in is adjacent to at least one vertex in . We denote the family of dominating sets of a graph with cardinality by . In this paper we introduce graphs with specific constructions, which are denoted by . We construct the dominating sets of by dominating sets of graphs , , and . As an example of , we consider . As a consequence, we obtain the recursive formula for the number of dominating sets of . 1. Introduction Let be a graph of order . For any vertex , the open neighborhood of is the set , and the closed neighborhood is the set . For a set , the open neighborhood is , and the closed neighborhood is . A set is a dominating set if , or equivalently, every vertex in is adjacent to at least one vertex in . The domination number is the minimum cardinality of a dominating set in , and the family of -sets is denoted by . For a detailed treatment of this parameter, the reader is referred to [1]. Let be the family of dominating sets of a graph with cardinality , and let . The domination polynomial of is defined as , where is the domination number of . 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 by . 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 and . As usual we use , for the smallest integer greater than or equal to and the largest integer less than or equal to , respectively. In this paper we denote the set simply by . 2. Dominating Sets of Graphs A path is a connected graph in which two vertices have degree 1, and the remaining vertices have degree 2. Let be the path with and ; see Figure 1(a). Figure 1: (a) The path ; (b) graph contains a simple path of length . In this section we introduce graphs with specific construction and study their dominating sets. Let be a path with vertices labeled by , for . Let be a graph obtained from by identifying a vertex of with an end vertex of . For example, if