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

Dominating Sets and Domination Polynomials of Paths

Saeid Alikhani1,2 and Yee-Hock Peng2,3

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

Received 13 November 2008; Accepted 12 March 2009

Academic Editor: Alexander Rosa

Copyright © 2009 Saeid Alikhani and Yee-Hock Peng. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

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.