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!
|
| _version_ | 1832556589506101248 |
|---|---|
| author | Saeid Alikhani Yee-Hock Peng |
| author_facet | Saeid Alikhani Yee-Hock Peng |
| author_sort | Saeid Alikhani |
| collection | DOAJ |
| description | 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. |
| format | Article |
| id | doaj-art-0a73552c30ce4ba6bfbe274f135cbff8 |
| institution | Kabale University |
| issn | 0161-1712 1687-0425 |
| language | English |
| publishDate | 2009-01-01 |
| publisher | Wiley |
| record_format | Article |
| series | International Journal of Mathematics and Mathematical Sciences |
| spelling | doaj-art-0a73552c30ce4ba6bfbe274f135cbff82025-02-03T05:44:50ZengWileyInternational Journal of Mathematics and Mathematical Sciences0161-17121687-04252009-01-01200910.1155/2009/542040542040Dominating Sets and Domination Polynomials of PathsSaeid Alikhani0Yee-Hock Peng1Department of Mathematics, Faculty of Science, Yazd University, 89195-741, Yazd, IranInstitute for Mathematical Research, University Putra Malaysia, 43400 UPM Serdang, MalaysiaLet 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.http://dx.doi.org/10.1155/2009/542040 |
| spellingShingle | Saeid Alikhani Yee-Hock Peng Dominating Sets and Domination Polynomials of Paths International Journal of Mathematics and Mathematical Sciences |
| title | Dominating Sets and Domination Polynomials of Paths |
| title_full | Dominating Sets and Domination Polynomials of Paths |
| title_fullStr | Dominating Sets and Domination Polynomials of Paths |
| title_full_unstemmed | Dominating Sets and Domination Polynomials of Paths |
| title_short | Dominating Sets and Domination Polynomials of Paths |
| title_sort | dominating sets and domination polynomials of paths |
| url | http://dx.doi.org/10.1155/2009/542040 |
| work_keys_str_mv | AT saeidalikhani dominatingsetsanddominationpolynomialsofpaths AT yeehockpeng dominatingsetsanddominationpolynomialsofpaths |