  A number of recent papers have considered signed graph Laplacians, a
generalization of the classical graph Laplacian, where the edge weights are
allowed to take either sign. In the classical case, where the edge weights are
all positive, the Laplacian is positive semi-definite with the dimension of the
kernel representing the number of connected components of the graph. In many
applications one is interested in establishing conditions which guarantee the
positive semi-definiteness of the matrix. In this paper we present an
inequality on the eigenvalues of a weighted graph Laplacian (where the weights
need not have any particular sign) in terms of the first two moments of the
edge weights. This bound involves the eigenvalues of the equally weighted
Laplacian on the graph as well as the eigenvalues of the adjacency matrix of
the line graph (the edge-to-vertex dual graph). For a regular graph the bound
can be expressed entirely in terms of the second eigenvalue of the equally
weighted Laplacian, an object that has been extensively studied in connection
with expander graphs and spectral measures of graph connectivity. We present
several examples including Erd\H{o}s-R\'enyi random graphs in the critical and
subcritical regimes, random large $d$-regular graphs, and the complete graph,
for which the inequalities here are tight.
