  We consider the problem of partitioning the node set of a graph into $k$ sets
of given sizes in order to \emph{minimize the cut} obtained using (removing)
the $k$-th set. If the resulting cut has value $0$, then we have obtained a
vertex separator. This problem is closely related to the graph partitioning
problem. In fact, the model we use is the same as that for the graph
partitioning problem except for a different \emph{quadratic} objective
function. We look at known and new bounds obtained from various relaxations for
this NP-hard problem. This includes: the standard eigenvalue bound, projected
eigenvalue bounds using both the adjacency matrix and the Laplacian, quadratic
programming (QP) bounds based on recent successful QP bounds for the quadratic
assignment problems, and semidefinite programming bounds. We include numerical
tests for large and \emph{huge} problems that illustrate the efficiency of the
bounds in terms of strength and time.
