Dominating Sets and Domination Polynomials of Cubic Paths

Let G = (V, E) be a simple graph. A set SV ⊆ is a dominating set of G, if every vertex in V – S is adjacent to at least one vertex in S. Let 3 Pn be the cubic path nP and let ( ) 3 n D P , i denote the family of all dominating sets of 3 Pn with cardinality i. Let ( ) 3, n d P i= | ( ) 3 n D P , i |. In this paper, we obtain a recursive formula for 3 n d(P ,i). Using this recursive formula, we construct the polynomial =   = ∑ n 3 3i nn i ni 7 (P ) d(P , D,ixi)x which we call the domination polynomial of Pn3 and obtain some properties of this polynomial.