Ars Combinatoria · 2014 · 14 citations · 1 references
Natural SciencesMathematicsAlgorithmsCombinatoricsComputational GeometryAlgebraic CombinatoricsDirected Acyclic GraphsGraph AlgorithmsGraph TheoryDominating Sets
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) = ∑n 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. AMS Classification: 05C38, 05C69.
1