Counting connected set partitions of graphs (Q625376)

Summary: Let \(G= (V,E)\) be a simple undirected graph with \(n\) vertices then a set partition \(\pi= \{V_1,\dots, 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 \(r\) is connected for \(1\leq j\leq k\). Define \(q_i(G)\) as the number of connected set partitions in \(G\) with \(i\) blocks. The partition polynomial is \(Q(G,x)= \sum^n_{i=0} 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^n_{i= 1} \sum^m_{j=1} q_{ij}(G)x^iy^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 \(\sharp P\)-hard.