Counting Connected Set Partitions of Graphs

Details Counting Connected Set Partitions of Graphs Counting Connected Set Partitions of Graphs

2010-05-11

arxiv.org/abs/1005.1726v2

The Electronic Journal of Combinatorics 18 (2011) #P14

Mathematics

Combinatorics

Scientific paper

Let $G=(V,E)$ be a simple undirected graph with $n$ vertices then a set partition $\pi=\{V_1, ..., 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^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.

Affiliated with

Also associated with

No associations

Rating

Counting Connected Set Partitions of Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Counting Connected Set Partitions of Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Counting Connected Set Partitions of Graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-383817