ACTA MATHEMATICA UNIVERSITATIS COMENIANAE

ACTA MATHEMATICA UNIVERSITATIS COMENIANAE

Vol. LXXIV, 2 (2005)
p. 185 - 198

Sharp upper bounds on the spectral radius of the Laplacian matrix of graphs
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₁ > d₂ > ... > 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):

V~ -------------------------- r(G) < 2e- (n- 1)dn + (dn- 1)mmax,

with equality if and only if G is a star graph or G is a regular graph.

In addition, we give two upper bounds for l(G):

V~ s um ----------(- sum -------)------------------------ { 2 + ni=1di(di-1)- 12 ni=1di-1 (2dn- 2)+(2dn- 3)(2d1- 2), 1.c(G) < if dn > 2, V~ s um n----------------- 2+ i=1 di(di- 1)- d1 + 1, if dn = 1,

where the equality holds if and only if G is a regular bipartite graph or G is a star graph, respectively.

2. l(G) < V~ -----[2e----n-2------------(----d--)]------
d1 + d21 + 4 n-1 + n-1d1 + (d1- dn) 1 - n1-1 mmax
-----------------------2------------------------- ,

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