The Laplacian quadratic form and edge connectivity of a graph

Abstract

Let G be a simple connected graph with associated positive semidefinite integral quadratic form Q(x) = \sum (x(i) â x(j))^2, where the sum is taken over all edges ij of G. It is showed that the minimum positive value of Q(x) for x â Z_n equals the edge connectivity of G. By restricting Q(x) to x â Z_{nâ1} Ã {0}, the quadratic form becomes positive definite. It is also showed that the number of minimal disconnecting sets of edges of G equals twice the number of vectors x â Z_{nâ1} Ã{0} for which the form Q attains its minimum positive value.