Abstract

Let G be a simple connected weighted graph on n vertices in which the edge weights are positive numbers. Denote by i ∼ j if the vertices i and j are adjacent and by wi,j the weight of the edge ij. Let wi = ∑j = 1 n wi, j. Let λ1 be the largest Laplacian eigenvalue of G. We first derive the upper boundλ1 ≤ underover(∑, j = 1, n) under(max, k ∼ j) wk, j .We call this bound the trivial upper bound for λ1. Our main result is{Mathematical expression}For any G, this new bound does not exceed the trivial upper bound for λ1. © 2006 Elsevier Inc. All rights reserved.