Home > Timetable > Contribution details


Counting Connected Sets and Connected Partitions of a Graph


  • Prof. Andrew VINCE

Primary authors


Two related enumeration problems on vertex labeled graphs will be discussed. Given a graph $G$, we introduce and investigate the number $C(G)$ of connected subsets of the vertex set and the number $P(G)$ of connected partitions of the vertex set. By {\it connected} we mean that the induced subgraphs are connected. The numbers $C(G)$ and $P(G)$ can be regarded as the graph analogs of the number of subsets and the number of set partitions, respectively, of an $n$-element set.