Setup: Consider a Laplacian (or Kirchoff) matrix $L = L^T \in \mathbb{R}^{n \times n}$ corresponding to a weighted, undirected and connected graph. That is, a matrix with $L_{ij} \leq 0$ for $i\neq j$ and $L_{ii} = -\sum_{j=1}^n L_{ij} > 0$. So $L$ has zero row sum, and is positive semidefinite with a simple eigenvalue at $0$.
It's well known that if you add a small positive (resp. negative) amount to any diagonal element of $L$, the zero eigenvalue is pushed into the right (resp. left) half plane.
Question: Consider a diagonal but indefinite matrix $B = \mathrm{diag}(b_{11},\ldots,b_{nn})$. What are sufficient conditions on $B$ such that $L + B$ is positive definite?
What I know: Obviously if $B$ was positive semi-definite the result would follow. I've found cases where a small negative $b_{ii}$ cannot be compensated for by a sufficiently large $b_{jj}$, so a condition of the form $Trace(B) >\!\!> 0$ won't work.
A Guess: Any negative element added at node $i$ must be corrected for with a positive addition at a (or several) nodes which are "sufficiently connected" in the graph to node i.
Thoughts appreciated! -John