The Enumeration of Vertex Induced Subgraphs with respect to the Number of Components

P. Tittmann, I. Averbouch, J. A. Makowsky

Inspired by the study of community structure in connection networks, we introduce the graph polynomial $Q(G;x,y)$, the bivariate generating function which counts the number of conn…