Graph Polynomials for the Numbers of Independent Sets and Bipartite Cuts for Undirected Graphs

R. L. Streit

The graph polynomial for the number of independent sets of size $k$ in a general undirected graph is shown to be equal to an elementary symmetric polynomial of the vertex monomials…