Counting Connected Partitions of Graphs

Abstract

Motivated by the theorem of Gy\H ori and Lovász, we consider the following problem. For a connected graph $G$ on $n$ vertices and $m$ edges determine the number $P(G,k)$ of unordered solutions of positive integers ${\sum }_{i=1}^k{m}_i=m$ such that every $m_i$ is realized by a connected subgraph $H_i$ of $G$ with $m_i$ edges such that ${\cup }_{i=1}^{k}E(H_i)=E(G)$. We also consider the vertex-partition analogue. We prove various lower bounds on $P(G,k)$ as a function of the number $n$ of vertices in $G$, as a function of the average degree $d$ of $G$, and also as the size ${\mathrm{CMC}}_r(G)$ of $r$-partite connected maximum cuts of $G$. Those three lower bounds are tight up to a multiplicative constant. We also prove that the number $\pi (G,k)$ of unordered $k$-tuples with ${\sum }_{i=1}^k{n}_i=n$, that are realizable by vertex partitions into $k$ connected parts of respective sizes $n_1,n_2,\dots ,n_k$, is $\Omega (d^{k-1})$.