Dominating sets and domination polynomials of paths (Q1028883)

Summary: Let \(G=(V,E)\) be a simple graph. A set \(S\subseteq V\) is a dominating set of \(G\), if every vertex in \(V\setminus S\) is adjacent to at least one vertex in \(S\). Let \(\mathcal P_{n}^{i}\) be the family of all dominating sets of a path \(P_{n}\) with cardinality \(i\), and let \(d(P_{n},j)=|\mathcal P_{n}^{j}|\). In this paper, we construct \(\mathcal P_{n}^{i}\), and obtain a recursive formula for \(d(P_{n},i)\). Using this recursive formula, we consider the polynomial \(D(P_{n},x)=\sum_{i=\lceil n/3\rceil}^{n}\, d(P_{n},i)x^{i}\), which we call domination polynomial of paths and obtain some properties of this polynomial.