Dominating sets and Domination polynomials of Cycles

2009/05/20 by ‎Saeid Alikhani, Saeid Alikhani, Alikhani, Saeid +3
Computer Science · Mathematics · #05C69 #11B83 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #math.CO #msc:05C69 #msc:11B83

paper · pdf · doi:10.48550/arxiv.0905.3268

13 pages. Accepted in http://www.ripublication.com/gjpam.htm

arxiv created 2009/05/20 · openalex publication_date 2009/05/20 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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

Related

• Cycles are determined by their domination polynomials
• Introduction to Domination Polynomial of a Graph
• The domination polynomial of powers of paths and cycles
• Domination polynomial of lexicographic product of specific graphs
• Some new results on the total domination polynomial of a graph