Article
Full entry |
PDF
(0.2 MB)
Feedback
PDF
(0.2 MB)
Feedback
Keywords:
Laplacian matrix; signless Laplacian matrix; normalized Laplacian matrix; characteristic polynomial
Laplacian matrix; signless Laplacian matrix; normalized Laplacian matrix; characteristic polynomial
Summary:
The Laplacian, signless Laplacian and normalized Laplacian characteristic polynomials of a graph are the characteristic polynomials of its Laplacian matrix, signless Laplacian matrix and normalized Laplacian matrix, respectively. In this paper, we mainly derive six reduction procedures on the Laplacian, signless Laplacian and normalized Laplacian characteristic polynomials of a graph which can be used to construct larger Laplacian, signless Laplacian and normalized Laplacian cospectral graphs, respectively.
References:
[1] Berge, C.: Principles of Combinatorics. Mathematics in Science and Engineering vol. 72. Academic Press New York (1971). MR 0270922
[2] Butler, S.: A note about cospectral graphs for the adjacency and normalized Laplacian matrices. Linear Multilinear Algebra 58 (2010), 387-390. DOI 10.1080/03081080902722741 | MR 2663439 | Zbl 1187.05046
[3] Chung, F. R. K.: Spectral Graph Theory. Regional Conference Series in Mathematics 92. American Mathematical Society Providence (1997). MR 1421568
[4] Grone, R., Merris, R.: Ordering trees by algebraic connectivity. Graphs Comb. 6 (1990), 229-237. DOI 10.1007/BF01787574 | MR 1081197 | Zbl 0735.05054
[5] Guo, J.: On the second largest Laplacian eigenvalue of trees. Linear Algebra Appl. 404 (2005), 251-261. DOI 10.1016/j.laa.2005.02.031 | MR 2149662 | Zbl 1066.05085
[6] Guo, J.-M.: On the Laplacian spectral radius of trees with fixed diameter. Linear Algebra Appl. 419 (2006), 618-629. MR 2277992 | Zbl 1118.05063
[7] Guo, J.-M.: A conjecture on the algebraic connectivity of connected graphs with fixed girth. Discrete Math. 308 (2008), 5702-5711. DOI 10.1016/j.disc.2007.10.044 | MR 2459389 | Zbl 1189.05085
[8] Liu, Y., Liu, Y.: The ordering of unicyclic graphs with the smallest algebraic connectivity. Discrete Math. 309 (2009), 4315-4325. DOI 10.1016/j.disc.2009.01.010 | MR 2519167 | Zbl 1189.05087
[9] Schwenk, A. J.: Computing the characteristic polynomial of a graph. Graphs and Combinatorics. Proceedings of the Capital Conference on Graph Theory and Combinatorics at the George Washington University, June 18-22, 1973. Lecture Notes in Mathematics 406 R. A. Bari et al. Springer Berlin (1974), 153-172. MR 0387126 | Zbl 0308.05121
[10] Shao, J. Y., Guo, J. M., Shan, H. Y.: The ordering of trees and connected graphs by algebraic connectivity. Linear Algebra Appl. 428 (2008), 1421-1438. MR 2388629 | Zbl 1134.05063
[11] Yuan, X. Y., Shao, J. Y., Zhang, L.: The six classes of trees with the largest algebraic connectivity. Discrete Appl. Math. 156 (2008), 757-769. DOI 10.1016/j.dam.2007.08.014 | MR 2397220 | Zbl 1137.05047
[12] Zhang, X. D.: Ordering trees with algebraic connectivity and diameter. Linear Algebra Appl. 427 (2007), 301-312. MR 2351361 | Zbl 1125.05067
Search
Partner of
