Jtdylktuy

I need a simple upper bound on the $lambda_1$ the largest Laplacian eigenvalue of $G$ (aka $L(G)$ matrix). $G$ is a connected weighted graph without any loop or multiple edges. I've search the literature and found some paper regarding this. For example:

$$
lambda_1 leq max_{i~j} left{lambda_1 (sum_{k:ksim i}w_{ik}) + sum_{k:ksim j}lambda_1(w_{jk}) right}
$$

which $w_{ij}$ is the weight between the node $i$ and $j$. Also it's been assumed that the laplacian eigenvalues are ordered as $lambda_1 geq ldots geq lambda_n = 0$. The literature is focused on giving thigher bounds while I need more simpler ones. Tightness is a good point but second priority.

• Weight in $G$ are all positive and between 0 and 1 i.e ($a_{ij} in [0,1]$)


• Being simpler in term of mathematical complexity and less dependency to various variables is far more important than tightness.


• Simpler also means have less computational complexity to be implemented. For example $lambda_1 underset{?}{leq} 2Delta$ which $Delta$ is the largest $G$'s degree is considered simple (let's suppose it's correct).

Given a graph $G$ with vertices $v_1, ldots, v_n$ and a set of weights $w_{ij} = w_{ji} in [0,1]$ assigned to edges $v_i v_j$.
The Laplacian matrix $L(G ; w)$ is defined by the formula:

$$L(G ; w)_{ij} = begin{cases}
a_i, & i = j\
-w_{ij},& i sim j\
0 & text{ otherwise }
end{cases}
quadtext{ where }quad a_i = sum_{k : ksim i} w_{ik}
$$

Since $sumlimits_{j=0}^n L(G;w)_{ij} = 0$ for each $i$, the row sum of $i^{th}$ row coincides with the diagonal element $a_i$.
$$R_i stackrel{def}{=} sum_{jne i} left|L(G;w)_{ij}right|
= sum_{j : j sim i} |-w_{ij}| = sum_{j : j sim i } w_{ij} = a_i$$

By Gershgorin circle theorem, the eigenvalues $lambda_1 ge cdots ge lambda_n$ are located inside the union of a bunch of closed discs:

$$lambda_1, ldots,lambda_n in bigcup_{i=1}^n bar{B}( a_i, R_i ) =
bigcup_{i=1}^n bar{B}( a_i, a_i )$$

Notice for any pair of non-negative numbers $r, s$, we have $bar{B}( r, r ) subset bar{B}( s, s )$ whenever $r le s$.

Above union is a single disc and
$$lambda_1, ldots, lambda_n in bar{B}( a_{max}, a_{max} )
quadtext{ where }quad a_{max} = max(a_1,ldots,a_i)$$

Since all $w_{ij} in [0,1]$, we have $a_{max} le Delta(G)$, the maximum degree of $G$. This leads to
$$lambda_1, ldots, lambda_n in bar{B}(Delta(G),Delta(G))$$
As a result, the largest eigenvalue $lambda_1$ is bounded from above by $2Delta(G)$.

Another simple one is given by Anderson, Morley, Eigenvalues of the Laplacian of a graph:

$$ lambda_1 leq max_{ij} d_i + d_j, $$

where $d_i = sum_{k: ksim i} w_{ik}$ is the weighted degree of node $i$.