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:k\sim i}w_{ik}) + \sum_{k:k\sim 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} 2\Delta$ 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} \quad\text{ where }\quad a_i = \sum_{k : k\sim i} w_{ik} $$
Since $\sum\limits_{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_{j\ne 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} ) \quad\text{ 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 $2\Delta(G)$.