On the two largest eigenvalues of trees

✍ Scribed by M. Hofmeister

• Publisher: Elsevier Science
• Year: 1997
• Tongue: English
• Weight: 650 KB
• Volume: 260
• Category: Article
• ISSN: 0024-3795
• DOI: 10.1016/s0024-3795(97)80004-3

✦ Synopsis

Very little is known about upper bounds for the largest eigenvalues of a tree that depend only on the vertex number. Starting from a classical upper bound for the largest eigenvalue, some refinements can be obtained by successively removing trees from consideration. The results can be used to characterize those trees that maximize the second largest eigenvalue. This corrects a result from the literature, and it includes a proof of a conjecture of Neumaier. The main tool for this endeavor is the theory of partial engenvectors. 0 Elsevier Science Inc., 1997 1. INTRODUCTION In this paper, we consider only connected finite graphs and, in particular, trees. If G is a graph with n vertices, then its adjacency matrix is denoted by A(G). Since this matrix is symmetric, all of its eigenvalues are real; we assume, without loss of generality, that they are ordered in decreasing order, i.e., A,(G) > A,(G) a h,(G) > -** > A,(G). Note that the largest eigenvalue is of multiplicity one, since A(G) is irreducible for connected graphs; this is part of the well-known Frobenius