On Dominating Sets and the Domination Polynomial

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 is denoted by D(G,x) is the generating polynomial for the counts of dominating sets of each cardinality. In this thesis we will consider four problems related to the domination polynomial. We begin by studying the optimality of domination polynomials. We will investigate the average order of dominating sets of graphs. We will explore the unimodality of the domination polynomials. Finally we will analyze the roots of domination polynomials.