On the Degree Polynomial of Graphs

Abstract

Graph polynomials encode graph theoretic information in the form of polynomials. These polynomials have been of interest for decades, for both graph theoretic insight and their mathematical properties. This thesis discusses one particular graph polynomial: the degree polynomial. This graph polynomial encodes the degree sequence of a graph, and has only recently appeared in the literature. We begin by examining basic properties of the degree polynomial, including special evaluations. Our focus is largely on roots of the degree polynomial: we explore how these roots compare to roots of polynomials with non-negative integer coefficients, their density, and how they are impacted by restricting certain graph parameters. The latter leads to bounds on the roots in terms of graph order. We also study these roots for a few families of graphs, being able to say much more about their roots. Possible extensions or generalizations of the degree polynomial are also briefly discussed.