Dominating Sets and Domination Polynomials of Paths
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,...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2009-01-01
|
| Series: | International Journal of Mathematics and Mathematical Sciences |
| Online Access: | http://dx.doi.org/10.1155/2009/542040 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Summary: | 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. |
|---|---|
| ISSN: | 0161-1712 1687-0425 |