In this paper, we explore the singular values of adjacency matrices {An} for a particular family {Gn} of graphs, known as broom trees. The singular values of a matrix M are defined to be the square roots of the eigenvalues of the symmetrized matrix MTM. The matrices we are interested in are the symmetrized adjacency matrices AnTAn and the symmetrized exponentiated adjacency matrices BnTBn = (eAn − I)T(eAn − I) of the graphs Gn. The application of these matrices in the HITS algorithm for Internet searches suggests that we study whether the largest two eigenvalues of AnTAn (or those of BnTBn) can become close or in fact coincide. We have shown that for one family of broom-trees, the ratio of the two largest eigenvalues of BnTBn as the number n of nodes (more specifically, the length l of the graph) goes to infinity is bounded below one. This bound shows that for these graphs, the second largest eigenvalue remains bounded away from the largest eigenvalue. For a second family of broom trees it is not known whether the same is true. However, we have shown that for that family a certain later eigenvalue remains bounded away from the largest eigenvalue. Our last result is a generalization of this latter result.
| Identifer | oai:union.ndltd.org:CLAREMONT/oai:scholarship.claremont.edu:hmc_theses-1189 |
| Date | 01 May 2006 |
| Creators | Powell, Tracy |
| Publisher | Scholarship @ Claremont |
| Source Sets | Claremont Colleges |
| Detected Language | English |
| Type | text |
| Format | application/pdf |
| Source | HMC Senior Theses |
Page generated in 0.0019 seconds