Cycles are determined by their domination polynomials

2009/08/23 by Saieed Akbari, Akbari, Saieed, Mohammad Reza Oboudi +1
Computer Science · Mathematics · #Advanced Differential Equations and Dynamical Systems #Advanced Graph Theory Research #Graph theory and applications #math.CO #msc:05C38 #msc:05C69

paper · pdf · doi:10.48550/arxiv.0908.3305

To appear in Ars Combinatoria

arxiv created 2009/08/23 · arxiv updated 2009/12/01

Abstract

Let G be a simple graph of order n. A dominating set of G is a set S of vertices of G so that every vertex of G is either in S or adjacent to a vertex in S. The domination polynomial of G is the polynomial D(G,x)=∑_i=1ⁿ d(G,i) xⁱ, where d(G,i) is the number of dominating sets of G of size i. In this paper we show that cycles are determined by their domination polynomials.

Related

• Dominating sets and Domination polynomials of Cycles
• The domination polynomial of powers of paths and cycles
• Introduction to Domination Polynomial of a Graph
• Domination polynomial of lexicographic product of specific graphs
• Some families of graphs whose domination polynomials are unimodal