Download PDF - Spectral integral variation of treesAll rights reserved. Copyright exceptions and limitations apply

ArticleOriginal scientific text

Title

Spectral integral variation of trees

Authors 1, 1

Affiliations

  1. School of Mathematics and Computational Science, Anhui University, Hefei, Anhui 230039, P.R. China

Abstract

In this paper, we determine all trees with the property that adding a particular edge will result in exactly two Laplacian eigenvalues increasing respectively by 1 and the other Laplacian eigenvalues remaining fixed. We also investigate a situation in which the algebraic connectivity is one of the changed eigenvalues.

Keywords

ENG
tree, Laplacian eigenvalues, spectral integral variation, algebraic connectivity

Bibliography

  1. D.M. Cvetković, M. Doob and H. Sachs, Spectra of Graphs-Theory and Applications (2nd Edn., VEB Deutscher Verlag d. Wiss., Berlin, 1982).
  2. Yi-Zheng Fan, On spectral integral variations of graph, Linear and Multilinear Algebra 50 (2002) 133-142, doi: 10.1080/03081080290019513.
  3. Yi-Zheng Fan, Spectral integral variations of degree maximal graphs, Linear and Multilinear Algebra 52 (2003) 147-154.
  4. M. Fiedler, Algebraic connectivity of graphs, Czechoslovak Math. J. 23 (1973) 298-305.
  5. M. Fiedler, A property of eigenvectors of nonnegative symmetric matrices and its applications to graph theory, Czechoslovak Math. J. 25 (1975) 619-633.
  6. R. Grone, R. Merris and V.S. Sunder, The Laplacian spectrum of a graph, SIAM J. Matrix Anal. Appl. 11 (1990) 218-238, doi: 10.1137/0611016.
  7. R. Grone and R. Merris, The Laplacian spectrum of a graph II, SIAM J. Discrete Math. 7 (1994) 229-237, doi: 10.1137/S0895480191222653.
  8. F. Harary and A.J. Schwenk, Which graphs have integral spectra? in: Graphs and Combinatorics, R.A. Bari and F. Harray eds. (Springer-Verlag, 1974), 45-51, doi: 10.1007/BFb0066434.
  9. S. Kirkland, A characterization of spectrum integral variation in two places for Laplacian matrices, Linear and Multilinear Algebra 52 (2004) 79-98, doi: 10.1080/0308108031000122506.
  10. R. Merris, Laplacian matrices of graphs: a survey, Linear Algebra Appl. 197/198 (1994) 143-176, doi: 10.1016/0024-3795(94)90486-3.
  11. R. Merris, Degree maximal graphs are Laplacian integral, Linear Algebra Appl. 199 (1994) 381-389, doi: 10.1016/0024-3795(94)90361-1.
  12. B. Mohar, The Laplacian spectrum of graphs, in: Y. Alavi et al. (eds.), Graph Theory, Combinatorics, and Applications (Wiley, New York, 1991) 871-898.
  13. W. So, Rank one perturbation and its application to the Laplacian spectrum of graphs, Linear and Multilinear Algebra 46 (1999) 193-198, doi: 10.1080/03081089908818613.
Discussiones Mathematicae Graph Theory
2006/26/1
Export to PBN, Opens in new tab
Pages:
49-58
Main language of publication
English
Received
2004-10-11
Accepted
2005-01-08
Published
2006

DOI: 10.7151/dmgt.1300

Exact and natural sciences