Counting Connected Set Partitions of Graphs

Let $G=(V,E)$ be a simple undirected graph with $n$ vertices then a set partition $\pi =\{V_1,\mathrm{.}\mathrm{.}\mathrm{.},V_k\}$ of the vertex set of $G$ is a connected set partition if each subgraph $G[V_j]$ induced by the blocks $V_j$ of $\pi$ is connected for $1\le j\le k$. Define $q_i(G)$ as the number of connected set partitions in $G$ with $i$ blocks. The partition polynomial is then $Q(G, x)=\sum_{i=0}^n q_{i}(G)x^i$. This paper presents a splitting approach to the partition polynomial on a separating vertex set $X$ in $G$ and summarizes some properties of the bond lattice. Furthermore the bivariate partition polynomial $Q(G,x,y)={\sum }_{i=1}^n{\sum }_{j=1}^m{q}_{ij}(G)x^i{y}^j$ is briefly discussed, where $q_{ij}(G)$ counts the number of connected set partitions with $i$ blocks and $j$ intra block edges. Finally the complexity for the bivariate partition polynomial is proven to be $\mathrm{♯}P$-hard.