A nontrivial upper bound on the largest Laplacian eigenvalue of weighted graphs (Q861028)

The author obtains an upper bound on the largest Laplacian eigenvalue of weighted graphs. Let \(G\) be a connected weighted graph on \(n\) vertices. The author denotes by \(w_{i,j}\) the weight of the edge \((i,j)\), \(i \sim j\) if the vertices \(i\) and \(j\) are adjacent and \(w_i=\sum_{i \sim j} w_{k,i}\). He also denotes by \(L(G)\) the Laplacian matrix of \(G\) and \(\lambda_1 \geq \lambda_2 \geq \cdots \lambda_{n-1}>\lambda_n=0\) the eigenvalues of \(L(G)\). The main result of the paper establishes the following upper bound on the largest Laplacian eigenvalue: \[ \lambda_1 \leq \tfrac{1}{2}\max_{i \sim j} \left\{w_i+w_j+ \sum_{k \sim i, k \not \sim j}w_{i,k}+ \sum_{k \sim j, k \not \sim i}w_{j,k}+ \sum_{k \sim i, k \not \sim j} | w_{i,k}-w_{j,k}| \right\}. \] This upper bound does not exceed \(\sum_{j=1}^n \max_{k \sim j} w_{k,j}\).