Dominating Sets and Domination Polynomials of Paths
Saeid Alikhani, Yee-Hock Peng · International Journal of Mathematics and Mathematical Sciences · 2009
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 family of all dominating sets of a path Pn with cardinality i, and let . In this paper, we construct , and obtain a recursive formula for d(Pn, i). Using this recursive formula, we consider the polynomial , which we call domination polynomial of paths and obtain some properties of this polynomial.