  The neighborhood polynomial of graph $G$ is the generating function for the
number of vertex subsets of $G$ of which the vertices have a common neighbor in
$G$. In this paper, we investigate the behavior of this polynomial under
several graph operations. Specifically, we provide an explicit formula for the
neighborhood polynomial of the graph obtained from a given graph $G$ by vertex
attachment. We use this result to propose a recursive algorithm for the
calculation of the neighborhood polynomial. Finally, we prove that the
neighborhood polynomial can be found in polynomial-time in the class of
$k$-degenerate graphs.
