International Journal of Mathematics and Mathematical Sciences
Volume 2009 (2009), Article ID 542040, 10 pages
doi:10.1155/2009/542040

Dominating sets and domination polynomials of paths

Saeid Alikhani1 and Yee-Hock Peng2

1Department of Mathematics, Faculty of Science, Yazd University, 89195-741, Yazd, Iran
 2Institute for Mathematical Research, University Putra Malaysia, 43400 UPM Serdang, Malaysia

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 𝒫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.