文章基本信息

标题：Dominating Sets and Domination Polynomials of Paths
本地全文：下载
作者：Saeid Alikhani ; Yee-Hock Peng
期刊名称：International Journal of Mathematics and Mathematical Sciences
印刷版ISSN：0161-1712
电子版ISSN：1687-0425
出版年度：2009
卷号：2009
DOI：10.1155/2009/542040
出版社：Hindawi Publishing Corporation
摘要：Let 𝐺=(𝑉,𝐸) be a simple graph. A set 𝑆⊆𝑉 is a dominating set of 𝐺, if every vertex in 𝑉\𝑆 is adjacent to at least one vertex in 𝑆. Let 𝒫𝑖𝑛 be the family of all dominating sets of a path 𝑃𝑛 with cardinality 𝑖, and let 𝑑(𝑃𝑛,𝑗)=|𝒫𝑗𝑛|. In this paper, we construct 𝒫𝑖𝑛, and obtain a recursive formula for 𝑑(𝑃𝑛,𝑖). Using this recursive formula, we consider the polynomial 𝐷(𝑃𝑛∑,𝑥)=𝑛𝑖=⌈𝑛/3⌉𝑑(𝑃𝑛,𝑖)𝑥𝑖, which we call domination polynomial of paths and obtain some properties of this polynomial.