# Graphs, groups, and more: celebrating Brian Alspach’s 80th and Dragan Marušič’s 65th birthdays

from 28 May 2018 to 1 June 2018
Koper
UTC timezone
Home > Timetable > Contribution details

# Counting Connected Sets and Connected Partitions of a Graph

## Speakers

• Prof. Andrew VINCE

## 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.