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

摘要

Let G be a simple connected weighted graph on n vertices in which the edge weights are positive numbers. Denote by i similar to j if the vertices i and j are adjacent and by wi,j the weight of the edge ij. Let w(i) = Sigma(n)(j=1) w(i,j). Let lambda(1) be the largest Laplacian eigenvalue of G. We first derive the upper bound lambda 1 <= Sigma(n)(j=1) max(k similar to j) w(k,j). We call this bound the trivial upper bound for lambda(1). Our main result is lambda 1 <= (1)/(2) max(i similar to j) {(wi + wj + Sigma k similar to i,k not similar to jwi,k + Sigma k similar to,k not similar to iwj,k)(+Sigma k similar to i.k similar to j vertical bar wi.k - wj.k vertical bar)}. For any G, this new bound does not exceed the trivial upper bound for lambda. (c) 2006 Elsevier Inc. All rights reserved.