Laplacian matrices of graphs: A survey. (English) Zbl 0802.05053

Merris, Russell

Linear Algebra Appl. 197-198, 143-176 (1994).

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)].

Reviewer: D.Cvetković (Beograd)

MSC:

05C50	Graphs and linear algebra (matrices, eigenvalues, etc.)
05-02	Research exposition (monographs, survey articles) pertaining to combinatorics
05C90	Applications of graph theory

Keywords:

adjacency matrix; Laplacian; algebraic connectivity; eigenvalues; spectrum

Citations:

Zbl 0265.05119; Zbl 0783.05073

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
[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, (Gunning, R. C., Problems in Analysis (1970), Princeton U.P), 195-199 · Zbl 0212.44903
[19]	Chung, F. R.K., Diameters and eigenvalues, J. Amer. Math. Soc., 2, 187-196 (1989) · Zbl 0678.05037
[21]	Collins, K. L., On a conjecture of Graham and Lovasz about distance matrices, Discrete Appl. Math., 25, 27-35 (1989) · Zbl 0724.05044
[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: 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
[29]	Cvetković, D. M.; Doob, M.; Gutman, I.; Torĝasev, A., Recent Results in the Theory of Graph Spectra (1988), North-Holland: North-Holland Amsterdam · Zbl 0634.05054
[30]	Cvetković, D. M.; Doob, M.; Sachs, H., Spectra of Graphs (1979), Academic: 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, (Internat. Ser. Numer. Math., 29 (1975), Birkhäuser: Birkhäuser Basel), 69-85 · Zbl 0331.05137
[41]	An algebraic approach to connectivity of graphs, (Recent Advances in Graph Theory (1975), Academia: Academia Prague), 193-196
[42]	Laplacian of graphs and algebraic connectivity, (Combinatorics and Graph Theory (1989), PWN: PWN Warsaw), 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: 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, (Bondy, J. A.; Murty, U. S.R., Progress in Graph Theory (1984), Academic: Academic New York), 281-293 · Zbl 0554.05059
[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, (Alavi, Y.; Lick, D. R., Theory and Applications of Graphs. Theory and Applications of Graphs, Lecture Notes in Math., 642 (1978), Springer-Verlag: Springer-Verlag Berlin), 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
[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
[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)
[68]	Harary, F.; Schwenk, A. J., Which graphs have integral spectra?, (Bari, R. A.; Harary, F., Graphs and Combinatorics. Graphs and Combinatorics, Lecture Notes in Math., 406 (1974), Springer-Verlag: Springer-Verlag Berlin), 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) · Zbl 0597.15015
[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
[84]	Marshall, A. W.; Olkin, I., Inequalities: Theory of Majorization and Its Applications (1979), Academic: 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
[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, (Alavi, Y.; Chartrand, G.; Ollermann, O. R.; Schwenk, A. J., Graph Theory, Combinatorics, and Applications (1991), Wiley: Wiley New York), 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, (IMA Preprint Ser. 939 (1992), Inst. for Math. Appl., Univ. of Minnesota: Inst. for Math. Appl., Univ. of Minnesota Minneapolis) · 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, (Grone, R., Current Trends in Matrix Theory (1987), Elsevier: Elsevier Amsterdam), 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, (King, R. B., Chemical Applications of Topology and Graph Theory (1983), Elsevier: Elsevier Amsterdam), 159-177
[118]	Predicting chemistry from topology, Sci. Amer, 255, 40-47 (Sept. 1986)
[119]	The role of the topological distance matrix in chemistry, (Trinajstić, N., Mathematics and Computational Concepts in Chemistry (1986), Horwood: Horwood Chichester), 295-306
[120]	Characterization of molecular branching using topological indices, (Ringesen, R. O., Applications of Discrete Mathematics (1988), SIAM: SIAM Philadelphia), 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 \(P_n\) 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, (Harary, F., New Directions in Graph Theory (1973), Academic: Academic New York), 275-307 · Zbl 0261.05102
[129]	Exactly thirteen connected cubic graphs have integral spectra, (Alavi, Y.; Lick, D. R., Theory and Applications of Graphs. Theory and Applications of Graphs, Lecture Notes in Math, 642 (1978), Springer-Verlag: Springer-Verlag Berlin), 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)
[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: CRC Press Boca Raton, Fla
[134]	Chemical Graph Theory, Vol. II (1983), CRC Press: 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
[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
[142]	Welsh, D., Matroids and their applications, (Beineke, L. W.; Wilson, R. J., Selected Topics in Graph Theory 3 (1988), Academic: Academic New York), 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, (Combinatorial Mathematics V. Combinatorial Mathematics V, Lecture Notes in Math., 622 (1977), Springer-Verlag: Springer-Verlag Berlin), 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, (Colloq. Math. Soc., 18 (1976), János Bolyai), 315-330
[151]	An estimate for the nonstatistic eigenvalues of doubly stochastic matrices, (IMA Preprint Ser. 902 (1991), Inst. for Math. Appl., Univ. of Minnesota)
[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
[155]	Grone, R., On the geometry and Laplacian of a graph, Linear Algebra Appl., 150, 167-178 (1991) · Zbl 0764.05058