Dominating Sets and Domination Polynomials of Paths

Abstract EN

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 ?ni be the family of all dominating sets of a path Pn with cardinality i, and let d(Pn,j)=|?nj|.

In this paper, we construct ?ni, and obtain a recursive formula for d(Pn,i).

Using this recursive formula, we consider the polynomial D(Pn,x)=∑i=⌈n/3⌉nd(Pn,i)xi, which we call domination polynomial of paths and obtain some properties of this polynomial.