  Partition problems in graphs are extremely important in applications, as
shown in the Data science and Machine learning literature. One approach is
spectral partitioning based on a Fiedler vector, i.e., an eigenvector
corresponding to the second smallest eigenvalue $a(G)$ of the Laplacian matrix
$L_G$ of the graph $G$. This problem corresponds to the minimization of a
quadratic form associated with $L_G$, under certain constraints involving the
$\ell_2$-norm. We introduce and investigate a similar problem, but using the
$\ell_1$-norm to measure distances. This leads to a new parameter $b(G)$ as the
optimal value. We show that a well-known cut problem arises in this approach,
namely the sparsest cut problem. We prove connectivity results and different
bounds on this new parameter, relate to Fiedler theory and show explicit
expressions for $b(G)$ for trees. We also comment on an $\ell_{\infty}$-norm
version of the problem.
