Home > Timetable > Contribution details

Contribution

Counting Connected Sets and Connected Partitions of a Graph

Speakers

  • Prof. Andrew VINCE

Primary authors

Content

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.