DOMINATION POLYNOMIALS: A BRIEF SURVEY AND ANALYSIS

Abstract

A dominating set S of a graph G of order n is a subset of the vertices of G such that every vertex is either in S or adjacent to a vertex of S. The domination polynomial of G, denoted D(G, x), is the generating polynomial for the number of dominating sets in G of each size. Two graphs G and H are considered D- equivalent if D(G, x) = D(H, x). The equivalence class of G, denoted [G], is the set of all graphs D-equivalent to G. We provide some results on constructing D-equivalent graphs as well as determine the equivalence class of paths. We also explore some bounds on the coefficients of D(G, x) for a given graph, and for some families of graphs. We conclude with a few open problems and possible research directions.