Perfect Dominating sets and Perfect Domination Polynomial of a Path

Abstract

Let  be a simple graph. A set  is a perfect dominating set of G, if every vertex  in  is adjacent to exactly one vertex in S. Let  be the family of all perfect dominating sets of a path  with cardinality , and let . In this paper, we construct  for a path  with  vertices and obtain a recursive formula of  . Using this recursive formula, we consider the polynomial   , which we call perfect domination polynomial of paths and obtain some properties of this polynomial.