Summary: Let be a simple graph. A set is a dominating set of , if every vertex in is adjacent to at least one vertex in . Let be the family of all dominating sets of a graph with cardinality , and be the graph obtained by appending a single pendant edge to each vertex of graph . We call a centipede, where is a path with vertices. In this paper we study the dominating sets of centipedes and obtain the number of dominating sets of . We show that , where and are respectively, cycle and arbitrary graph of order .
|05C69||Dominating sets, independent sets, cliques|