×

zbMATH — the first resource for mathematics

Laplace eigenvalues of graphs—a survey. (English) Zbl 0783.05073
In this reporting paper, several applications of Laplace eigenvalues of graphs in graph theory and combinatorial optimization are outlined. They include the edge density in cuts, partitioning with eigenvectors, Laplacian on hypergraphs, Hamiltonicity and \(\zeta\)-functions on graphs. The bibliography contains 93 papers and books related to these items.

MSC:
05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
05C80 Random graphs (graph-theoretic aspects)
05C45 Eulerian and Hamiltonian graphs
05C65 Hypergraphs
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Aldous, D., On the time taken by random walks on finite groups to visit every state, Zw, 62, 361-374, (1983) · Zbl 0488.60011
[2] Aldous, D., Hitting times for random walks on vertex-transitive graphs, Math. proc. Cambridge philos. soc., 106, 179-191, (1989) · Zbl 0668.05043
[3] Aldous, D., Lower bounds for covering times for reversible Markov chains and random walks on graphs, J. theoret. probab., 2, 91-100, (1989) · Zbl 0684.60055
[4] Alon, N., Eigenvalues and expanders, Combinatorica, 6, 83-96, (1986) · Zbl 0661.05053
[5] Alon, N.; Milman, V.D., Λ_{1}, isoperimetric inequalities for graphs and superconcentrators, J. combin. theory ser. B, 38, 73-88, (1985) · Zbl 0549.05051
[6] Beck, J.; Sos, V.T., Discrepancy theory, () · Zbl 0851.11043
[7] Bien, F., Constructions of telephone networks by group representations, Notices amer. math. soc., 36, 5-22, (1989) · Zbl 1194.90021
[8] Biggs, N.L., Algebraic graph theory, (1974), Cambridge Univ. Press Cambridge · Zbl 0501.05039
[9] Bolla, M., Spectra, Euclidean representations and vertex-colourings of hypergraphs, (1989), preprint
[10] Boppana, R.B., Eigenvalues and graph bisection: an average-case analysis, 28th ann. symp. FOCS, 286-294, (1987), Los Angeles, CA
[11] Broder, A.Z.; Karlin, A.R., Bounds on the cover time, J. theoret. probab., 2, 101-120, (1989) · Zbl 0681.60063
[12] Broder, A.; Shamir, E., On the second eigenvalue of random regular graphs, 28th ann. symp. on FOCS, 286-294, (1987), Los Angeles, CA
[13] Brooks, R., Combinatorial problems in spectral geometry, (), 14-32
[14] Brouwer, A.E.; Cohen, A.M.; Neumaier, A., Distance regular graphs, (1989), Springer Berlin · Zbl 0747.05073
[15] Burger, M., Small eigenvalues of Riemann surfaces and graphs, Math. Z., 205, 395-420, (1990) · Zbl 0729.58050
[16] Cheeger, J., A lower bound for the smallest eigenvalue of the Laplacian, (), 195-199 · Zbl 0212.44903
[17] Cheng, C.S., Maximizing the total number of spanning trees in a graph: two related problems in graph theory and optimum design theory, J. combin. theory ser. B, 31, 240-248, (1981) · Zbl 0475.05050
[18] Chiu, P., Cubic Ramanujan graphs, (1989), preprint
[19] F.R.K. Chung, Quasi-random classes of hypergraphs, Random Struct. Algor., to appear. · Zbl 0739.05066
[20] Chung, F.R.K.; Graham, R.L., Quasi-random hypergraphs, Random struct. algor., 1, 105-124, (1990) · Zbl 0708.05044
[21] Chung, F.R.K.; Graham, R.L.; Wilson, R.M., Quasi-random graphs, Combinatorica, 9, 345-362, (1989) · Zbl 0715.05057
[22] Chung, F.R.K.; Tetali, P., Communication complexity and quasi-randomness, (1990), preprint
[23] Constantine, G., On the optimality of block designs, Ann. inst. statist. math., 38, 161-174, (1986) · Zbl 0588.62123
[24] Constantine, G., Combinatorial theory and statistical design, (1987), Wiley New York · Zbl 0617.05002
[25] Constantine, G.M., Graph complexity and the Laplacian matrix in blocked experiments, Linear and multilinear algebra, 28, 49-56, (1990) · Zbl 0714.05040
[26] Cvetković, D.M.; Doob, M.; Gutman, I.; Torgašev, A., Recent results in the theory of graph spectra, () · Zbl 0634.05054
[27] Cvetković, D.M.; Doob, M.; Sachs, H., Spectra of graphs—theory and applications, (1979), Academic Press New York
[28] Delorme, C.; Poljak, S., Laplacian eigenvalues and the maximum cut problem, (1990), preprint · Zbl 0797.90107
[29] Diaconis, P.; Stroock, D., Geometric bounds for eigenvalues of Markov chains, (1989), preprint
[30] Feit, W.; Higman, G., The non-existence of certain generalized polygons, J. algebra, 1, 114-131, (1964) · Zbl 0126.05303
[31] Fiedler, M., Algebraic connectivity of graphs, Czech. math. J., 23, 98, 298-305, (1973) · Zbl 0265.05119
[32] Fiedler, M., A property of eigenvectors of nonnegative symmetric matrices and its application to graph theory, Czech. math. J., 25, 100, 619-633, (1975) · Zbl 0437.15004
[33] Fiedler, M., Laplacian of graphs and algebraic connectivity, (), 57-70
[34] Fiedler, M., Absolute algebraic connectivity of trees, Linear and multilinear algebra, 26, 85-106, (1990) · Zbl 0737.05043
[35] Fiedler, M., A minimax problem for graphs and its relation to generalized doubly stochastic matrices, Linear and multilinear algebra, 27, 1-23, (1990) · Zbl 0748.05065
[36] Fischer, R.A., An examination of the different possible solutions of a problem in incomplete blocks, Ann. eugen., 10, 52-75, (1940)
[37] Friedman, J.; Kahn, J.; Szemeredi, E., On the second eigenvalue in random regular graphs, Proc. 21st annual ACM symp. theory comput., 587-598, (1989), Seattle
[38] J. Friedman and A. Wigderson, 1990, preprint.
[39] Füredi, Z.; Komlós, J., The eigenvalues of random symmetric matrices, Combinatorica, 1, 233-241, (1981) · Zbl 0494.15010
[40] Grone, R.; Merris, R., Ordering trees by algebraic connectivity, Graphs combin, 6, 229-237, (1990) · Zbl 0735.05054
[41] Grone, R.; Merris, R., Coalescence, majorization, edge valuations and the Laplacian spectra of graphs, Linear and multilinear algebra, 27, 139-146, (1990) · Zbl 0735.05055
[42] Grone, R.; Merris, R.; Sunder, V.S., The Laplacian spectrum of a graph, SIAM J. matrix anal., 11, 218-238, (1990) · Zbl 0733.05060
[43] Grone, R.; Zimmermann, G., Large eigenvalues of the Laplacian, Linear and multilinear algebra, 28, 45-47, (1990) · Zbl 0714.05039
[44] Heilmann, O.J.; Lieb, E.H., Theory of monomer-dimer systems, Commun. math. phys., 25, 190-232, (1972) · Zbl 0228.05131
[45] Juhász, F., On the spectrum of a random graph, (), 313-316
[46] Juhász, F., On a method of cluster analysis, Z. angew. math. mech., 64, T335-T336, (1984) · Zbl 0579.62044
[47] Juhász, F., On the theoretical backgrounds of cluster analysis based on the eigenvalue problem of the association matrix, Statistics, 20, 573-581, (1989) · Zbl 0688.62039
[48] Juhász, F.; Mályusz, K., Problems of cluster analysis from the viewpoint of numerical analysis, (), 405-415 · Zbl 0467.62055
[49] Juvan, M.; Mohar, B., Optimal linear labelings and eigenvalues of graphs, Discrete appl. math., 36, 153-168, (1992) · Zbl 0759.05087
[50] Juvan, M.; Mohar, B., Laplace eigenvalues and bandwidth-type invariants of graphs, (1990), preprint
[51] Kahn, J.N.; Linial, N.; Nisan, N.; Saks, M.E., On the cover time of random walks on graphs, J. theoret. probab., 2, 121-128, (1989) · Zbl 0681.60064
[52] Li, W., Abelian Ramanujan graphs, (1989), preprint
[53] Lovász, L., Topological and algebraic methods in graph theory, (), 1-14
[54] Lovász, L., On the Shannon capacity of a graph, IEEE trans. inform. theory, 25, 1-7, (1979) · Zbl 0395.94021
[55] Lubotzky, A.; Phillips, R.; Sarnak, P., Ramanujan graphs, Combinatorica, 8, 261-277, (1988) · Zbl 0661.05035
[56] Margulis, G.A., Explicit group-theoretical constructions of combinatorial schemes and their application to the design of expanders and superconcentrators, Problemy peredachi informatsii, Problems inform. transmission, 24, 39-46, (1988), English translation: · Zbl 0708.05030
[57] Merris, R., An edge version of the matrix-tree theorem and the Wiener index, Linear and multilinear algebra, 25, 291-296, (1989) · Zbl 0723.05049
[58] Merris, R., Almost all trees are co-de-two too, (1989), preprint
[59] Merris, R., The distance spectrum of a tree, J. graph theory, 14, 365-369, (1990) · Zbl 0734.05037
[60] Mohar, B., The Laplacian spectrum of graphs, (), 871-898 · Zbl 0840.05059
[61] Mohar, B., Isoperimetric numbers of graphs, J. combin. theory, 47, 274-291, (1989), Ser. B · Zbl 0719.05042
[62] Mohar, B., A domain monotonicity theorem for graphs and Hamiltonicity, Discrete appl. math., 36, 169-177, (1992) · Zbl 0765.05071
[63] Mohar, B., Eigenvalues, diameter, and Mean distance in graphs, Graphs combin., 7, 53-64, (1991) · Zbl 0771.05063
[64] Mohar, B.; Poljak, S., Eigenvalues and the MAX-cut problem, Czech. math. J., 40, 343-352, (1990) · Zbl 0724.05046
[65] Palacios, J.L., Bounds on expected hitting times for a random walk on a connected graph, Linear algebra appl., 141, 241-252, (1990) · Zbl 0711.05040
[66] Pizer, A.K., Ramanujan graphs and Hecke operators, Bull. amer. math. soc., 23, 127-137, (1990), (N.S.) · Zbl 0752.05035
[67] 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
[68] Powers, D.L., Graph partitioning by eigenvectors, Linear algebra appl., 101, 121-133, (1988) · Zbl 0666.05056
[69] Rubinfeld, R., The cover time of a regular expander is O(n log n), Inform. process. lett., 35, 49-51, (1990) · Zbl 0706.68059
[70] Sinclair, A.; Jerrum, M., Approximate counting, uniform generation and rapidly mixing Markov chains, Inform. comput., 82, 93-133, (1989) · Zbl 0668.05060
[71] T. Sunada, ж-Functions on graphs, Private communication. · Zbl 0655.58031
[72] Sunderam, V.S.; Winkler, P., Fast information sharing in a distributed system, (1988), preprint
[73] Watkins, W., The Laplacian matrix of a graph: unimodular congruence, Linear and multilinear algebra, 28, 35-43, (1990) · Zbl 0744.05032
[74] Adin, R., Counting colorful multi-dimensional trees, (1989), preprint · Zbl 0773.05038
[75] Brightwell, G.; Winkler, P., Maximum hitting time for random walks on graphs, Random str. algor., 1, (1990) · Zbl 0744.05044
[76] Chung, F.R.K.; Graham, R.L., Cohomological aspects of hypergraphs, (1991), preprint · Zbl 0772.05073
[77] Chung, F.R.K., The Laplacian of a hypergraph, (1991), preprint
[78] Delorme, C.; Poljak, S., Combinatorial properties and the complexity of a MAX-cut approximation, () · Zbl 0786.05057
[79] Delorme, C.; Poljak, S., The performance of an eigenvalue bound on the MAX-cut problem in some classes of graphs, Colloque Marseille, (1990) · Zbl 0786.05057
[80] Delorme, C.; Solé, P., Diameter, covering radius and eigenvalues, European J. combin., 12, 95-108, (1991) · Zbl 0737.05067
[81] Dyer, M.; Frieze, A.; Kannan, R., A random polynomial-time algorithm for approximating the volume of convex bodies, J. assoc. comput. Mach., 38, 1-17, (1991) · Zbl 0799.68107
[82] Friedland, S., Lower bounds for the first eigenvalue of certain M-matrices associated with graphs, (1991), preprint
[83] S.W. Hadley, F. Rendl and H. Wolkowicz, Symmetrization of non-symmetric quadratic assignment problems and the Hoffman-Wielandt inequality, Linear Algebra Appl., to appear. · Zbl 0767.90070
[84] Hadley, S.W.; Rendl, F.; Wolkowicz, H., Bounds for the quadratic assignment problem using continuous optimization techniques, Proc. combinatorial optimization, 237-248, (1990), Waterloo
[85] Hadley, S.W.; Rendl, F.; Wolkowicz, H., A new lower bound via projection for the quadratic assignment problem, (1991), preprint · Zbl 0767.90059
[86] Lovász, L.; Simonovits, M., The mixing rate of Markov chains, an isoperimetric inequality, and computing the volume, (1990), preprint
[87] Mohar, B.; Poljak, S., Eigenvalues in combinatorial optimization, (1992), preprint
[88] Narasimhan, G.; Manber, R., A generalization of lovász θ function, DIMACS series in discrete math. comp. sci., 1, 19-27, (1990)
[89] Poljak, S., Polyhedral and eigenvalue approximations of the MAX-cut problem, (), Submitted to Proc. Conf. ‘Sets, Graphs and Numbers’ (Budapest, 1991) · Zbl 0792.05102
[90] Poljak, S.; Rendl, F., Computing the MAX-cut by eigenvalues, () · Zbl 0807.90099
[91] Rendl, F.; Wolkowicz, H., Applications of parametric programming and eigenvalue maximization to the quadratic assignment problem, Math. progr., 53, 63-78, (1992) · Zbl 0751.90051
[92] Rendl, F.; Wolkowicz, H., A projection technique for partitioning the nodes of a graph, () · Zbl 0841.90120
[93] P. Solé, Expanding and forwarding, submitted.
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.