Counting connected set partitions of graphs

MaRDI QIDQ625376zbMATH OpenFDO

Authors Frank Simon, Peter Tittmann, Martin Trinks

Publication date 17 February 2011

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1005.1726, http://www.emis.de/journals/EJC/Volume_18/Abstracts/v18i1p14.html

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

bond latticebounded tree-width, \(\sharp P\)-hardchromatic polynomialgraph theorypartition polynomialsplitting formula

Mathematics Subject Classification ID

Graph polynomials (05C31)

Abstract: Let $G=(V,E)$ be a simple undirected graph with $n$ vertices then a set partition $pi=V_1,\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 $1lejlek$. Define $q_i(G)$ as the number of connected set partitions in $G$ with $i$ blocks. The partition polynomial is then $Q(G,x)=su{m}_{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)=su{m}_{i=1}^{n}su{m}_{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 $sharpP$-hard.

Review text

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.

Recommendations

• scientific article; zbMATH DE number 6813595
• Compositions of complements of graphs
• On the complexity of partitioning graphs into connected subgraphs
• scientific article; zbMATH DE number 4139799
• A partition of connected graphs

Cited in

(10)

• A partition of connected graphs
• A recurrence for counting graphical partitions
• Compositions of complements of graphs
• Counting List Matrix Partitions of Graphs
• scientific article; zbMATH DE number 6813595 (Why is no real title available?)
• Harary polynomials
• scientific article; zbMATH DE number 6322891 (Why is no real title available?)
• A graph polynomial arising from community structure (extended abstract)
• The enumeration of vertex induced subgraphs with respect to the number of components
• Counting connected partitions of graphs

This page was built for publication: Counting connected set partitions of graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q625376)