  We address the problem of partitioning a vertex-weighted connected graph into
$k$ connected subgraphs that have similar weights, for a fixed integer $k\geq
2$. This problem, known as the \emph{balanced connected $k$-partition problem}
($BCP_k$), is defined as follows. Given a connected graph $G$ with nonnegative
weights on the vertices, find a partition $\{V_i\}_{i=1}^k$ of $V(G)$ such that
each class $V_i$ induces a connected subgraph of $G$, and the weight of a class
with the minimum weight is as large as possible. It is known that $BCP_k$ is
$NP$-hard even on bipartite graphs and on interval graphs. It has been largely
investigated under different approaches and perspectives. On the practical
side, $BCP_k$ is used to model many applications arising in police patrolling,
image processing, cluster analysis, operating systems and robotics. We propose
three integer linear programming formulations for the balanced connected
$k$-partition problem. The first one contains only binary variables and a
potentially large number of constraints that are separable in polynomial time.
Some polyhedral results on this formulation, when all vertices have unit
weight, are also presented. The other formulations are based on flows and have
a polynomial number of constraints and variables. Preliminary computational
experiments have shown that the proposed formulations outperform the other
formulations presented in the literature.
