**
ACTA MATHEMATICA UNIVERSITATIS COMENIANAE **

p. 185 - 198

K. Ch. Das

**Abstract.** 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):

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.

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