Bounds On The Eigenvalues Of Trees With An M-Matching And Square Root Graph

Let G be a connected finite simple graph with n vertices v1, v2, ... , vn. Its adjacency matrix A(G) = (aij) is defined to be the nxn matrix (aij), where if vi is adjacent to Vj otherwise.The characteristic polynomial of G is just | xI - A(G) | . Since A(G) is a real symmetric matix , all of its eigenvalues are real. We assume, without loss of generality, that they are ordered in decreasing order, i.e.,and call them the eigenvalues of G.The rich results about bounds on the eigenvalues have been obtained when the graph is a tree. But very little is given about lower bound on the second largest eigenvalue of a tree with an m-matching. In this paper, the above content is investigated. In section 1 of chapter 2, a lower bound on the second largest eigenvalues of a class of trees with an m-matching is presented by comparing the largest root of a monic polynomial with that of another monic polynomial. In section 2 of chapter 2, a new proof of a Theorem in [6] which is about upper bound on the largest eigenvalue of a tree with an m-matching is raised by applying monotonicity of a function , such that the new proof is very short and clear in comparison with the original proof. In chapter 3, a new lass of graphs are discussed. Let d(vi) be the degree of vertex Vi(i = 1,2, ... , v). Set d(G) = G is said to be a square root graph if d(G) is one of the eigenvectors of G (the eigenvectors of A(G) are said to be the eigenvectors of the graph G), that is, if there exists a constant A such that the relation A(G)d(G) = λd(G) is satisfied. By induction a conjecture which was presented by Ivan Gutman in [25] is proved, therefore an elegant characterization of square root graph is given. The main results are the following.Theorem Let T₂k^* be a tree on 2k vertices with a (2t + l)-matching, k≥2t+l, thenwhere the trees B(k,t) and T₂k^* are shown in Fig3 and Fig6, respectively.