Real-Rooted Neighbourhood Polynomials of Unbounded Degree

The neighbourhood polynomial of a graph counts its vertex subsets with a common neighbour, according to their size. We construct trees of every prescribed maximum degree whose neighbourhood polynomials have only simple negative roots. This answers a question of Day, including its proposed strengthening to trees. For maximum degree at least three, the trees can be chosen to have their nonleaf vertices on a path and to have no vertices of degree two. The construction works backwards from a desired polynomial: after translating the variable by one, nonnegative coefficients specify the numbers of vertices of each degree. A reciprocal-sum condition on prescribed negative roots is exactly what makes these degree counts nonnegative. Scaling the counts then gives real-rooted neighbourhood polynomials with explicitly controlled root limits. We give a uniform construction, an explicit sufficient scaling threshold, and a characterization of all coefficient limits at fixed maximum degree after normalization by the number of vertices. We also prove that a graph without four-cycles and with a real-rooted neighbourhood polynomial has a vertex of every degree from three to its maximum degree.