On the Neighbourhood Polynomial

Abstract

The neighbourhood polynomial of a graph is the generating function for the neighbourhood complex, which contains all subsets of vertices which have a common neighbour. We begin with some formulas for computing the neighbourhood polynomial. We then show a relation between the neighbourhood polynomial of one graph and the domination polynomial of its complement, and prove that computing the neighbourhood polynomial is NP-hard. Concerning the roots of the neighbourhood polynomial, we consider when all the roots are real and what bounds we can place on them. We show the rational roots of neighbourhood polynomials are exactly those numbers of the form -1/2n for natural numbers n. We also answer the question of the closure of the neighbourhood roots, finding the negative real line for the real roots and the complex plane for the complex roots. Finally, we use random graphs to show that almost all neighbourhood polynomials have nonreal roots.