Dominating Sets and Domination Polynomials of Square of Paths

Abstract

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 square of the Path and let denote the family of all dominating sets of with cardinality i . Let . In this paper, we obtain a recursive formula for . Using this recursive formula, we construct the polynomial, , which we call domination polynomial of and obtain some properties of this polynomial.