Abstract

Let G be a simple graph. In this paper, we obtain a sequence (b p)p=1? of upper bounds on the largest eigenvalue ?1(G) of the Laplacian matrix of G. Then, we show that this sequence converges to ?1(G) and that (b 2p)p=0? is a monotone strictly decreasing sequence except if G is a complete graph or G is a star graph or G is a regular complete bipartite graph. For these graphs, b p = ?1(G) for all p. The bounds b1 and b2 are discussed. © 2003 Elsevier Inc. All rights reserved.