On spectral bounds for cutsets (Q1849996)

Let \(G\) be a simple and connected graph. A \(k\)-vertex separator (\(k\)-edge separator) is a subset of vertices (edges) whose deletion separates the vertex (edge) set of \(G\) into two parts of equal cardinality, that are at distance greater than \(k\) in \(G\). Using \(k\)-alternating polynomials, defined by \textit{M. A. Fiol, E. Garriga} and \textit{J. L. A. Yebra} [J. Comb. Theory, Ser. B 67, 48-61 (1996; Zbl 0857.05101)], the authors obtain a lower bound on the minimum cardinality of a \(k\)-vertex separator (\(k\)-edge separator) in terms of the Laplacian eigenvalues of \(G\). As a consequence, they obtain new proofs for the well-known lower bounds for the bandwidth and the bipartition width of a graph.