Dominating sets and Domination polynomials of Cycles

By Saeid Alikhani, Yee-Hock Peng. 2009

50 citations recorded by the source corpus.

Let G=(V,E) be a simple graph. A set S\subset V is a dominating set of G, if every vertex in V\S is adjacent to at least one vertex in S. Let {\mathcal C}_n^i be the family of dominating sets of a cycle C_n with cardinality i, and let d(C_n,i) = |{\mathcal C}_n^i. In this paper, we construct {\mathcal C}_n^i, and obtain a recursive formula for d(C_n, i). Using this recursive formula, we consider the polynomial D(C_n, x) = \sum_{i=1}^n d(C_n, i)x^i, which we call domination polynomial of cycles and obtain some properties of this polynomial.

Subfields: Computational Theory and Mathematics, Geometry and Topology

View Paper: https://www.semanticscholar.org/paper/b8c4cab2e91335f0b5666b86ce7fbf4c71d4f6a9