Let G = ( V,E ) be a simple connected graph with n vertices and e edges. Assume that the vertices are ordered such that d 1 > d 2 > ... > d n , where d i is the degree of v i for i = 1 , 2 , ... ,n and the average of the degrees of the vertices adjacent to v i is denoted by m i . Let m max be the maximum of m i ’s for i = 1 , 2 , ... ,n . Also, let r ( G ) denote the largest eigenvalue of the adjacency matrix and l ( G ) denote the largest eigenvalue of the Laplacian matrix of a graph G . In this paper, we present a sharp upper bound on r ( G ): with equality if and only if G is a star graph or G is a regular graph. l. 89 In addition, we give two upper bounds for l(G): where the equality holds if and only if G is a regular bipartite graph or G is a star graph, respectively. 2. l(G) < , with equality if and only if G is a regular bipartite graph. Keywords: Graph, adjacency matrix, Laplacian matrix, spectral radius, upper bound. AMS Subject classification: 05C50. Download: Adobe PDF Compressed Postscript Version to read: Adobe PDF Acta Mathematica Universitatis Comenianae Institute of Applied Mathematics Faculty of Mathematics, Physics and Informatics Comenius University 842 48 Bratislava, Slovak Republic Telephone: + 421-2-60295755 Fax: + 421-2-65425882 e-Mail: amuc@fmph.uniba.sk Internet: www.iam.fmph.uniba.sk/amuc © Copyright 2005, ACTA MATHEMATICA UNIVERSITATIS COMENIANAE