×

zbMATH — the first resource for mathematics

Laplacian matrices of graphs: A survey. (English) Zbl 0802.05053
Let \(A(G)\) be the adjacency matrix and \(D(G)\) the diagonal matrix of vertex degrees of a graph \(G\). The matrix \(L(G)= D(G)- A(G)\) is called the Laplacian (matrix) of \(G\). The matrix \(L(G)\) is also known as the admittance matrix or the Kirchhoff matrix of \(G\). The name Laplacian is fully justified by the fact that \(L(G)\) is a discrete analog of the Laplacian operator from calculus. \(L(G)\) is a positive semi-definite matrix and its second smallest eigenvalue is called the algebraic connectivity of \(G\), as introduced by M. Fiedler [Czech. Math. J. 23, 298-305 (1973; Zbl 0265.05119)]. By the well-known matrix tree theorem, \(L(G)\) is related to the number of spanning trees of \(G\). During the last ten years the eigenvalues of \(L(G)\) have been intensively studied including their applications in chemistry and physics.
The paper under review is a well-written expository paper on graph Laplacians. The section titles read: 1. Introduction, 2. The spectrum, 3. The algebraic connectivity, 4. Congruence and equivalence, 5. Chemical applications, 6. Immanants. There are 155 references.
An expository sequel to this paper, which is written by the same author, is going to appear in Linear and Multilinear Algebra. There is also a good review on graph Laplacians by B. Mohar [Discrete Math. 109, No. 1-3, 171-183 (1992; Zbl 0783.05073)].

MSC:
05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
05-02 Research exposition (monographs, survey articles) pertaining to combinatorics
05C90 Applications of graph theory
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Aihara, J., Why aromatic compounds are stable, Sci. amer., 266, 62-68, (Mar. 1992)
[2] Alon, N., Eigenvalues and expanders, Combinatorica, 6, 83-96, (1986) · Zbl 0661.05053
[3] Alon, N.; Galil, Z.; Milman, V.D., Better expanders and superconcentrators, J. algorithms, 8, 337-347, (1987) · Zbl 0641.68102
[4] Alon, N.; Milman, V.D., Λ_{1}, isoperimetric inequalities for graphs, and superconcentrators, J. combin. theory ser. B, 38, 73-88, (1985) · Zbl 0549.05051
[5] Anderson, W.N.; Morley, T.D., Eigenvalues of the Laplacian of a graph, Linear and multilinear algebra, 18, 141-145, (1985) · Zbl 0594.05046
[6] Balaban, A.T., Chemical graphs, Theoret. chim. acta (berl.), 53, 355-375, (1979)
[7] Bapat, R.B., A bound for the permanent of the Laplacian matrix, Linear algebra appl., 74, 219-223, (1986) · Zbl 0587.15010
[8] Bapat, R.B.; Constantine, G., An enumerating function for spanning forests and color restrictions, Linear algebra appl., 173, 231-237, (1992) · Zbl 0804.05052
[9] Berman, K.A., Bicycles and spanning trees, SIAM J. algebraic discrete methods, 7, 1-12, (1986) · Zbl 0588.05016
[10] Bien, F., Constructions of telephone networks by group representations, Notices amer. math. soc., 36, 5-22, (1989) · Zbl 1194.90021
[11] Biggs, N., Algebraic graph theory, (1974), Cambridge U.P · Zbl 0284.05101
[12] P. Botti and R. Merris, Almost all trees share a complete set of immanantal polynomials, J. Graph Theory, to appear. · Zbl 0782.05038
[13] Botti, P.; Merris, R.; Vega, C., Laplacian permanents of trees, SIAM J. discrete math., 5, 460-466, (1992) · Zbl 0773.05076
[14] Brualdi, R.A.; Goldwasser, J.L., Permanent of the Laplacian matrix of trees and bipartite graphs, Discrete math., 48, 1-21, (1984) · Zbl 0533.05043
[15] Bussemaker, F.C.; Cvetković, D.M., There are exactly 13 connected, cubic, integral graphs, Univ. beograd publ. elektrotehn. fak. ser. mat. fiz., 544-576, 43-48, (1976) · Zbl 0357.05064
[16] Chaiken, S., A combinatorial proof of the all minors matrix tree theorem, SIAM J. algebraic discrete methods, 3, 319-329, (1982) · Zbl 0495.05018
[17] Chaiken, S.; Kleitman, D.J., Matrix tree theorems, J. combin. theory ser. A, 24, 377-381, (1978) · Zbl 0376.05032
[18] Cheeger, J., A lower bound for the smallest eigenvalue of the Laplacian, (), 195-199 · Zbl 0212.44903
[19] Chung, F.R.K., Diameters and eigenvalues, J. amer. math. soc., 2, 187-196, (1989) · Zbl 0678.05037
[20] F. R. K. Chung, V. Faber, and T. Manteuffel, An upper bound on the diameter of a graph from eigenvalues associated with its Laplacian, manuscript. · Zbl 0808.05072
[21] Collins, K.L., On a conjecture of graham and lovasz about distance matrices, Discrete appl. math., 25, 27-35, (1989) · Zbl 0724.05044
[22] Factoring distance matrix polynomials, Discrete Math., to appear. · Zbl 0788.05065
[23] Private communication.
[24] Constantine, G.M., Schur convex functions on the spectra of graphs, Discrete math., 45, 181-188, (1983) · Zbl 0527.05050
[25] Combinatorial theory and statistical design, (1987), Wiley New York · Zbl 0617.05002
[26] Graph complexity and the Laplacian matrix in blocked experiments, Linear and multilinear algebra, 28, 49-56, (1990) · Zbl 0714.05040
[27] Cvetković, D.M., Cubic integral graphs, Univ. beograd publ. elektrotehn. fak. ser. mat. fiz., 498-541, 107-113, (1975) · Zbl 0315.05125
[28] D.M. Cvetković and M. Doob, Developments in the theory of graph spectra, Linear and Multilinear Algebra 18:153-181. · Zbl 0615.05039
[29] Cvetković, D.M.; Doob, M.; Gutman, I.; Torĝasev, A., Recent results in the theory of graph spectra, (1988), North-Holland Amsterdam · Zbl 0634.05054
[30] Cvetković, D.M.; Doob, M.; Sachs, H., Spectra of graphs, (1979), Academic New York
[31] Dinic, E.A.; Kelmans, A.K.; Zaitsev, M.A., Nonisomorphic trees with the same T-polynomial, Inform. process. lett., 6, 73-76, (1977) · Zbl 0369.05023
[32] Edelberg, M.; Garey, M.R.; Graham, R.L., On the distance matrix of a tree, Discrete math., 14, 23-31, (1976) · Zbl 0328.05103
[33] Eichinger, B.E., Elasticity theory. I. distribution functions for perfect phantom networks, Macromolecules, 5, 496-505, (1972)
[34] Configuration statistics of Gaussian molecules, Macromolecules, 13, 1-11, (1980)
[35] Random elastic networks. I. computer simulation of linked stars, J. chem. phys., 75, 1964-1979, (1981)
[36] Faria, I., Permanental roots and the star degree of a graph, Linear algebra appl., 64, 255-265, (1985) · Zbl 0559.05041
[37] Fiedler, M., Algebraic connectivity of graphs, Czechoslovak math. J., 23, 298-305, (1973) · Zbl 0265.05119
[38] Eigenvectors of acyclic matrices, Czechoslovak math. J., 25, 607-618, (1975) · Zbl 0325.15014
[39] A property of eigenvectors of nonnegative symmetric matrices and its application to graph theory, Czecholovak math. J., 25, 619-633, (1975) · Zbl 0437.15004
[40] Algebraische zusammenhangszahl der graphen und ihre numerische bedeutung, (), 69-85
[41] An algebraic approach to connectivity of graphs, (), 193-196
[42] Laplacian of graphs and algebraic connectivity, (), 57-70, Banach Center Publ. 25
[43] Absolute algebraic connectivity of trees, Linear and multilinear algebra, 26, 85-106, (1990) · Zbl 0737.05043
[44] A geometric approach to the Laplacian matrix of a graph, (12 November 1991), Inst. for Math. Appl Minneapolis
[45] Fiedler, M.; Sedláček, J., O W-basich orientovaných grafu̇ (in Czech), Čas. Pěst mat., 83, 214-225, (1958)
[46] Fischer, M.E., On hearing the shape of a drum, J. combin. theory, 1, 105-125, (1966) · Zbl 0139.43302
[47] Forsman, W.C., Graph theory and the statistics and dynamics of polymer chains, J. chem. phys., 65, 4111-4115, (1976)
[48] Friedland, S., Maximality of the monomial group, Linear and multilinear algebra, 18, 1-7, (1985) · Zbl 0594.20037
[49] Quadratic forms and the graph isomorphism problem, Linear algebra appl., 150, 423-442, (1991) · Zbl 0734.05062
[50] Lower bounds for the first eigenvalue of certain M-matrices associated with graphs, Linear algebra appl., 172, 71-84, (1992) · Zbl 0784.15010
[51] Godsil, C., Real graph polynomials, (), 281-293
[52] Goldwasser, J.L., Permanent of the Laplacian matrix of trees with a given matching, Discrete math., 61, 197-212, (1986) · Zbl 0653.05047
[53] Goulden, I.P.; Jackson, D.M., The enumeration of directed closed Euler trails and directed Hamiltonian circuits by Lagrangian methods, European J. combin., 2, 131-135, (1981) · Zbl 0465.05050
[54] Graham, R.L.; Lovász, L., Distance matrix polynomials of trees, (), 186-190 · Zbl 0413.05030
[55] Distance matrix polynomials of trees, Adv. in math., 29, 60-88, (1978) · Zbl 0382.05023
[56] Graham, R.L.; Pollak, H.O., On the addressing problem for loop switching, Bell system tech. J., 50, 2495-2519, (1971) · Zbl 0228.94020
[57] Gromov, M.; Milman, V.D., A topological application of the isoperimetric inequality, Amer. J. math., 105, 843-854, (1983) · Zbl 0522.53039
[58] Grone, R.; Merris, R., Algebraic connectivity of trees, Czechoslovak math. J., 37, 660-670, (1987) · Zbl 0681.05022
[59] Cutpoints, lobes and the spectra of graphs, Portugal. math., 45, 181-188, (1988) · Zbl 0652.05035
[60] Ordering trees by algebraic connectivity, Graphs combin., 6, 229-237, (1990) · Zbl 0735.05054
[61] Coalescence, majorization, edge valuations and the Laplacian spectra of graphs, Linear and multilinear algebra, 27, 139-146, (1990) · Zbl 0735.05055
[62] The Laplacian spectrum of a graph II, SIAM J. Discrete Math., to appear. · Zbl 0795.05092
[63] Grone, R.; Merris, R.; Sunder, V.S., The Laplacian spectrum of a graph, SIAM J. matrix anal. appl., 11, 218-238, (1990) · Zbl 0733.05060
[64] R. Grone, R. Merris, and W. Watkins, Laplacian unimodular equivalence of graphs, in Combinatorial and Graph-Theoretic Problems in Linear Algebra (R. Brualdi, S. Friedland, and V. Klee, Eds.), IMA Vol. Math. Appl. 50, Springer-Verlag, New York, to appear. · Zbl 0791.05074
[65] Grone, R.; Zimmermann, G., Large eigenvalues of the Laplacian, Linear and multilinear algebra, 28, 45-47, (1990) · Zbl 0714.05039
[66] Gutman, I., Graph-theoretical formulation of Forsman’s equations, J. chem. phys., 68, 1321-1322, (1978)
[67] I. Gutman and D.H. Rouvray, A new theorem for the Wiener molecular branching index of trees with perfect matchings, Comput. and Chem., to appear.
[68] Harary, F.; Schwenk, A.J., Which graphs have integral spectra?, (), 45-51
[69] Hattori, Y., Nonisomorphic graphs with the same T-polynomial, Inform. process. lett., 22, 133-134, (1986) · Zbl 0618.05042
[70] Hosoya, H., Topological index. A newly proposed quantity characterizing the topological nature of structural isomers of saturated hydrocarbons, Bull. chem. soc. Japan, 44, 2332-2339, (1971)
[71] Hosoya, H.; Murakami, M.; Gotoh, M., Distance polynomial and characterization of a graph, Nat. sci. rep. ochanomizu univ., 24, 27-34, (1973) · Zbl 0273.05127
[72] Johnson, C.R.; Merris, R.; Pierce, S., Inequalities involving immanants and diagonal products for H-matrices, Portugal. math., 43, 43-54, (1985-1986)
[73] Juhasz, F., The asymptotic behavior of Fiedler’s algebraic connectivity of graphs, Discrete math., 96, 59-63, (1991) · Zbl 0755.05076
[74] Kac, M., Can one hear the shape of a drum, Amer. math. monthly, 73, 1-23, (1966) · Zbl 0139.05603
[75] Kel’mans, A.K., Properties of the characteristic polynomial of a graph, Kibernet. na službu kommunizmu, 4, 27-41, (1967), (in Russian)
[76] Kelmans, A.K.; Chelnokov, V.M., A certain polynomial of a graph and graphs with an extremal number of trees, J. combin. theory ser. B, 16, 197-214, (1974) · Zbl 0277.05104
[77] Kirchhoff, G., Über die auflösung der gleichungen, auf welche man bei der untersuchung der linearen verteilung galvanischer ströme geführt wird, Ann. phys. chem., 72, 497-508, (1847)
[78] Lewin, M., A generalization of the matrix-tree theorem, Math. Z., 181, 55-70, (1982) · Zbl 0478.05036
[79] Lorenzini, D.J., Arithmetical graphs, Math. ann., 285, 481-501, (1989) · Zbl 0662.14008
[80] A finite group attached to the Laplacian of a graph, Discrete math., 91, 277-282, (1991) · Zbl 0755.05079
[81] Lovász, L., On the Shannon capacity of a graph, IEEE trans. inform. theory, 25, 1-7, (1979) · Zbl 0395.94021
[82] Maas, C., Transportation in graphs and the admittance spectrum, Discrete appl. math., 16, 31-49, (1987) · Zbl 0612.90038
[83] M. Malek, Conversion of the permanent into the determinant, manuscript.
[84] Marshall, A.W.; Olkin, I., Inequalities: theory of majorization and its applications, (1979), Academic New York · Zbl 0437.26007
[85] Maurer, S.B., Matrix generalizations of some theorems on trees, cycles and cocycles in graphs, SIAM J. appl. math., 30, 143-148, (1976) · Zbl 0364.05021
[86] McKay, B.D., On the spectral characterisation of trees, Ars combin., 3, 219-232, (1977) · Zbl 0404.05045
[87] The expected eigenvalue distribution of a large regular graph, Linear algebra appl., 40, 203-216, (1981) · Zbl 0468.05039
[88] Private communication.
[89] Merris, R., Two problems involving Schur functions, Linear algebra appl., 10, 155-162, (1975) · Zbl 0304.15001
[90] The Laplacian permanental polynomial for trees, Czechoslovak math. J., 32, 397-403, (1982) · Zbl 0506.05044
[91] Single-hook characters and Hamiltonian circuits, Linear and multilinear algebra, 4, 21-35, (1983) · Zbl 0526.20008
[92] The second immanantal polynomial and the centroid of a graph, SIAM J. algebraic discrete methods, 7, 484-503, (1986) · Zbl 0605.05009
[93] Characteristic vertices of trees, Linear and multilinear algebra, 22, 115-131, (1987) · Zbl 0636.05021
[94] An edge version of the matrix-tree theorem and the Wiener index, Linear and multilinear algebra, 25, 291-296, (1989) · Zbl 0723.05049
[95] The distance spectrum of a tree, J. graph theory, 14, 365-369, (1990) · Zbl 0734.05037
[96] The number of eigenvalues greater than two in the Laplacian spectrum of a graph, Portugal. math., 48, 345-349, (1991) · Zbl 0731.05037
[97] Unimodular equivalence of graphs, Linear algebra appl., 173, 181-189, (1992) · Zbl 0763.05071
[98] Merris, R.; Rebman, K.R.; Watkins, W., Permanental polynomials of graphs, Linear algebra appl., 38, 273-288, (1981) · Zbl 0474.05049
[99] Merris, R.; Watkins, W., Inequalities and identities for generalized matrices, Linear algebra appl., 64, 223-242, (1985) · Zbl 0563.15006
[100] Michalski, M., Branching extent and spectra of trees, Publ. inst. math., 39, 35-43, (1986) · Zbl 0603.05027
[101] Mohar, B., Laplacian matrices of graphs, Preprint ser. dept. math. univ. E. K. Ljubljana, 26, 385-392, (1988)
[102] Isoperimetric inequalities, growth, and the spectra of graphs, Linear algebra appl., 103, 119-131, (1988) · Zbl 0658.05055
[103] Isoperimetric numbers of graphs, J. combin. theory ser. B, 47, 274-291, (1989) · Zbl 0719.05042
[104] The Laplacian spectrum of graphs, (), 871-898 · Zbl 0840.05059
[105] Eigenvalues, diameter, and Mean distance in graphs, Graphs combin., 7, 53-64, (1991) · Zbl 0771.05063
[106] Mohar, B.; Pisanski, T., How to compute the Wiener index of a graph, J. math. chem., 2, 267-277, (1988)
[107] Mohar, B.; Poljak, S., Eigenvalues and the MAX-cut problem, Czechoslovak math. J., 40, 343-352, (1990) · Zbl 0724.05046
[108] Eigenvalues in combinatorial optimization, () · Zbl 0806.90104
[109] Motoc, I.; Balaban, A.T., Topological indices: intercorrelations, physical meaning, correlational ability, Rev. roumaine chim., 26, 593-600, (1981)
[110] Neuburger, N.A.; Eichinger, B.E., Computer simulation of the dynamics of trifunctional and tetrafunctional end-linked random elastic networks, J. chem. phys., 83, 884-891, (1985)
[111] Nilli, A., On the second eigenvalue of a graph, Discrete math., 91, 207-210, (1991) · Zbl 0771.05064
[112] Pierce, S., Permanents of correlation matrices, (), 247-249
[113] Polansky, O.E.; Bonchev, D., Theory of the Wiener number of a graph. II. transfer graphs and some of their metric properties, Match, 25, 3-39, (1990) · Zbl 0768.05091
[114] Pothen, A.; Simon, H.D.; Liou, K.-P., Partitioning sparse matrices with eigenvectors of graphs, SIAM J. matrix anal. appl., 11, 430-452, (1990) · Zbl 0711.65034
[115] Protter, M., Can one hear the shape of a drum? revisited, SIAM rev., 29, 185-197, (1987) · Zbl 0645.35074
[116] Read, R.C., An introduction to chromatic polynomials, J. combin. theory, 4, 52-71, (1968) · Zbl 0173.26203
[117] Rouvray, D.H., Should we have designs on topological indices, (), 159-177
[118] Predicting chemistry from topology, Sci. amer, 255, 40-47, (Sept. 1986)
[119] The role of the topological distance matrix in chemistry, (), 295-306
[120] Characterization of molecular branching using topological indices, (), 176-178
[121] The challenge of characterizing branching in molecular species, Discrete appl. math., 19, 317-338, (1988)
[122] Ruch, E.; Gutman, I., The branching extent of graphs, J. combin. inform. system sci., 4, 285-295, (1979) · Zbl 0461.05057
[123] Ruzieh, S.N.; Powers, D.L., The distance spectrum of the path Pn and the first distance eigenvector of connected graphs, Linear and multilinear algebra, 28, 75-81, (1990) · Zbl 0728.05043
[124] de Sa, E.M., Note on graphs and weakly cyclic matrices, Discrete math., 34, 275-281, (1981) · Zbl 0486.05017
[125] Schur, I., Über eine klasse von mittelbildungen mit anwendungen die determinanten, Sitzungsber. Berlin. math. gesellschaft, 22, 9-20, (1923) · JFM 49.0054.01
[126] Über endliche gruppen und hermitesche formen, Math. Z., 1, 184-207, (1918) · JFM 46.0174.03
[127] Schuster, S., Interpolating theorem for the number of end-vertices of spanning trees, J. graph theory, 7, 203-208, (1983) · Zbl 0482.05032
[128] Schwenk, A.J., Almost all trees are cospectral, (), 275-307 · Zbl 0261.05102
[129] Exactly thirteen connected cubic graphs have integral spectra, (), 516-553
[130] Shy, L.Y.; Eichinger, B.E., Large computer simulations on elastic networks: small eigenvalues and eigenvalue spectra of the Kirchhoff matrix, J. chem. phys., 90, 5179-5189, (1989)
[131] W. So, Rank one perturbation and its application to the Laplacian spectrum of a graph, manuscript. · Zbl 0935.05065
[132] Trent, H.M., A note on the enumeration and listing of all maximal trees of a connected linear graph, Proc. nat. acad. sci. U.S.A., 40, 1004-1007, (1954) · Zbl 0055.42204
[133] Trinajstić, N., Chemical graph theory, Vol. I, (1983), CRC Press Boca Raton, Fla
[134] Chemical graph theory, Vol. II, (1983), CRC Press Boca Raton, Fla
[135] Turner, J., Generalized matrix functions and the graph isomorphism problem, SIAM J. appl. math., 16, 520-536, (1968) · Zbl 0185.51701
[136] de Verdiére, Y.C., Sur un nouvel invariant des graphes et un critère de planarité, J. combin. theory ser. B, 50, 11-21, (1990) · Zbl 0742.05061
[137] Spectres de variétés Riemanniennes et spectres de graphes, manuscri
[138] Vrba, A., The permanent of the Laplacian matrix of a bipartite graph, Czechoslovak math. J., 36, 397-403, (1982)
[139] Principal subpermanents of the Laplacian matrix, Linear and multilinear algebra, 19, 335-346, (1986) · Zbl 0598.05050
[140] Watkins, W., The Laplacian matrix of a graph: unimodular congruence, Linear and multilinear algebra, 28, 35-43, (1990) · Zbl 0744.05032
[141] Unimodular congruence of the Laplacian matrix of a graph, Linear Algebra Appl., to appear. · Zbl 0807.05055
[142] Welsh, D., Matroids and their applications, (), 43-70
[143] Whitney, H., A logical expansion in mathematics, Bull. amer. math. soc., 38, 572-579, (1932) · JFM 58.0605.08
[144] 2-isomorphic graphs, Amer. J. math., 55, 245-254, (1933) · JFM 59.1235.01
[145] Cameron, P.J.; Goethals, J.M.; Seidel, J.J.; Shult, E.E., Line graphs, root systems, and elliptic geometry, J. algebra, 43, 305-327, (1976) · Zbl 0337.05142
[146] Cipra, B., You can’t hear the shape of a drum, Science, 255, 1642-1643, (27 Mar. 1992)
[147] Godsil, C.; Holton, D.A.; McKay, B., The spectrum of a graph, (), 91-117 · Zbl 0371.05013
[148] Gordon, C.; Webb, D.L.; Wolpert, S., One cannot hear the shape of a drum, Bull. amer. math. soc., 27, 134-138, (1992) · Zbl 0756.58049
[149] Goulden, I.P.; Jackson, D.M., Immanants of combinatorial matrices, J. algebra, 148, 305-324, (1992) · Zbl 0756.15009
[150] Fiedler, M., Aggregation in graphs, (), 315-330
[151] An estimate for the nonstatistic eigenvalues of doubly stochastic matrices, ()
[152] Seidel, J.J., Distance matrices and Lorentz space, Workshop vladimir USSR, 1-2, (Aug. 1991)
[153] Sjogren, J.A., Cycles and spanning trees, Math. comput. modelling, 15, 87-102, (1991) · Zbl 0751.05061
[154] I. Faria, Multiplicity of integer roots of polynomials of graphs, Linear Algebra Appl., to appear. · Zbl 0843.05074
[155] Grone, R., On the geometry and Laplacian of a graph, Linear algebra appl., 150, 167-178, (1991) · Zbl 0764.05058
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.