Skip to main content
SpringerLink
Log in

Some applications of Laplace eigenvalues of graphs

  • Chapter
Graph Symmetry

Part of the book series: NATO ASI Series ((ASIC,volume 497))

Abstract

In the last decade important relations between Laplace eigenvalues and eigenvectors of graphs and several other graph parameters were discovered. In these notes we present some of these results and discuss their consequences. Attention is given to the partition and the isoperimetric properties of graphs, the max-cut problem and its relation to semidefinite programming, rapid mixing of Markov chains, and to extensions of the results to infinite graphs.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution
Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 169.00
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 219.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info
Hardcover Book
USD 219.99
Price excludes VAT (USA)
  • Durable hardcover edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

References

  1. F. Alizadeh, Interior point methods in semidefinite programming with applications to combinatorial optimization, SIAM J. Optim. 5 (1995), 13 – 51.

    Article  MathSciNet  MATH  Google Scholar 

  2. N. Alon, Eigenvalues and expanders, Combinatorica 6 (1986), 83 – 96.

    Article  MathSciNet  MATH  Google Scholar 

  3. N. Alon, V. D. Milman, A,i isoperimetric inequalities for graphs and superconcentrators, J. Combin. Theory Ser. B 38 (1985), 73 – 88.

    Article  MathSciNet  MATH  Google Scholar 

  4. S. Aurora, C. Lund, R. Motwani, M. Sudan, M. Szegedy, Proof verification and hardness of approximation problems, Proc. 33rd Ann. Sympos. FOCS, 1992, 14 – 23.

    Google Scholar 

  5. I. Bârâny, Z. Füredi, Computing the volume is difficult, Discrete Comput. Geom., 2 (1987), 319 – 326.

    Article  MathSciNet  MATH  Google Scholar 

  6. S. T. Barnard, H. D. Simon, A fast multilevel implementation of recursive spectral bisection for partitioning unstructured problems, Technical Report RNR-92–033, NASA Ames Res. Center, 1992.

    Google Scholar 

  7. D. Bayer, P. Diaconis, Trailing the dovetail shuffle to its lair, Ann. Appl. Probab. 2 (1992), 294 – 313.

    Article  MathSciNet  MATH  Google Scholar 

  8. N. L. Biggs, Algebraic Graph Theory ( 2nd edition ), Cambridge University Press, Cambridge, 1993.

    Google Scholar 

  9. J. A. Bondy, U. S. R. Murty, Graph Theory with Applications, North Holland/Elsevier, Amsterdam, 1976.

    Google Scholar 

  10. R. B. Boppana, Eigenvalues and graph bisection: An average case analysis, 28th Ann. Sympos. Found. Comp. Sci., IEEE, 1987, 280 – 285.

    Google Scholar 

  11. A. Z. Broder, How hard is to marry at random? (On the approximation of the permanent), Proc. 18th ACM STOC, 1986, 50–58. Erratum in Proc. 20th ACM STOC, 1988, 551.

    Google Scholar 

  12. R. Brooks, Spectral geometry and the Cheeger constant, in: Expanding Graphs, (J. Friedman, ed.), DIMACS Ser. Discrete Math. Theoret. Comput. Sci. 10, Amer. Math. Soc., Providence, RI, 1993, 5 – 19.

    Google Scholar 

  13. P. Buser, Geometry and Spectra of Compact Riemann Surfaces, Birkhäuser, Boston, 1992.

    Google Scholar 

  14. A. Cayley, A theorem on trees, Quart. J. Math. 23 (1889), 376 – 378.

    Google Scholar 

  15. P. K. Chan, M. Schlag, J. Zien, Spectral k-way ratio cut partitioning and clustering, Proc. Symp. Integrated Systems, 1993.

    Google Scholar 

  16. I. Chavel, Eigenvalues in Riemannian Geometry, Academic Press, San Diego, 1984.

    MATH  Google Scholar 

  17. J. Cheeger, A lower bound for the smallest eigenvalue of the Laplacian, in: Problems in Analysis (R.C. Gunnig, ed. ), Princeton University Press, 1970, 195 – 199.

    Google Scholar 

  18. F. R. K. Chung, Laplacians of graphs and Cheeger’s inequalities, in: Combinatorics, Paul Erdös is Eighty, Vol. 2, Janos Bolyai Math. Soc., Budapest, 1996, 157 – 172.

    Google Scholar 

  19. F. R. K. Chung, E. G. Coffman, M. I. Reiman, B. E. Simon, On the capacity and vertex-forwarding index of communication networks, IEEE Trans. Inform. Theory 33 (1987), 224 – 232.

    Article  MathSciNet  MATH  Google Scholar 

  20. F. R. K. Chung, P. Tetali, Isoperimetric inequalities for Cartesian products of graphs, submitted to Combin. Probab. Comput., 1996.

    Google Scholar 

  21. D. M. Cvetkovic, M. Doob, I. Gutman, A. Torgasev, Recent Results in the Theory of Graph Spectra, Ann. Discrete Math. 36, North-Holland, 1988.

    Google Scholar 

  22. D. M. Cvetkovic, M. Doob, H. Sachs, Spectra of Graphs, Academic Press, New York, 1979.

    Google Scholar 

  23. C. Delorme, S. Poljak, Laplacian eigenvalues and the maximum cut problem, Math. Programming 62 (1993), 557 – 574.

    Article  MathSciNet  MATH  Google Scholar 

  24. C. Delorme, S. Poljak, Combinatorial properties and the complexity of a max-cut approximation, European J. Combin. 14 (1993), 313 – 333.

    Article  MathSciNet  MATH  Google Scholar 

  25. P. Diaconis, Group Representations in Probability and Statistics, IMS Lecture Notes-Monograph Ser. 11, Hayward, CA, 1988.

    Google Scholar 

  26. P. Diaconis, M. Shahshahani, Generating a random permutation with random transpositions, Z. Wahrsch. Verw. Gebiete 57 (1981), 159 – 179.

    Article  MathSciNet  MATH  Google Scholar 

  27. P. Diaconis, D. Stroock, Geometric bounds for eigenvalues of Markov chains, Ann. Appl. Probab. 1 (1991), 36 – 61.

    Article  MathSciNet  MATH  Google Scholar 

  28. W. E. Donath, A. J. Hoffman, Lower bounds for the partitioning of graphs, IBM J. Res. Develop. 17 (1973), 420 – 425.

    Article  MathSciNet  MATH  Google Scholar 

  29. P. G. Doyle, J. L. Snell, Random Walks and Electric Networks, Math. Assoc. of America, Washington, DC, 1984.

    Google Scholar 

  30. M. E. Dyer, A. Frieze, R. Kannan, A random polynomial-time algorithm for approximating the volume of convex bodies, J. Assoc. Comput. Mach. 38 (1991), 1 – 17.

    Article  MathSciNet  MATH  Google Scholar 

  31. U. Feige, M. X. Goemans, Approximating the value of two prover proof systems, with applications to MAX 2SAT and MAX DICUT, Proc. Third Israel Sympos. Theory of Computing and Systems, 1995, 182 – 189.

    Google Scholar 

  32. W. Feller, An Introduction to Probability Theory and Its Applications, Wiley, New York, 1968.

    MATH  Google Scholar 

  33. M. Fiedler, Algebraic connectivity of graphs, Czechoslovak Math. J. 23 (98) (1973), 298 – 305.

    MathSciNet  Google Scholar 

  34. M. Fiedler, A property of eigenvectors of nonnegative symmetric matrices and its application to graph theory, Czechoslovak Math. J. 25 (100) (1975), 619 – 633.

    MathSciNet  Google Scholar 

  35. M. Fiedler, Laplacian of graphs and algebraic connectivity, in: Combinatorics and Graph Theory (Z. Skupien and M. Borowiecki, eds.), Banach Center Publ. 25, PWN, Warsaw, 1989, 57 – 70.

    Google Scholar 

  36. P. A. Fillmore, J. G. Stampfli, J. P. Williams, On the essential numerical range, the essential spectrum, and a problem of Halmos, Acta Sci. Math. (Szeged) 33 (1972), 179 – 192.

    MathSciNet  MATH  Google Scholar 

  37. FBR] G. Finke, R. E. Burkard and F. Rendl, Quadratic assignment problems, in: Surveys in Combinatorial Optimization (S. Martello et al., eds.), Ann. Discrete Math. 31 (1987), 61–82.

    Google Scholar 

  38. E. Fglner, On groups with full Banach mean values, Math. Scand. 3 (1955), 243 – 254.

    MathSciNet  Google Scholar 

  39. A. Frieze, M. Jerrum, Improved approximation algorithms for MAX k-CUT and MAX BISECTION, Proc. 4th IPCO, Springer-Verlag, Berlin, 1995.

    Google Scholar 

  40. M. R. Garey, D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, San Francisco, 1979.

    MATH  Google Scholar 

  41. M. R. Garey, D. S. Johnson, R. L. Stockmeyer, Some simplified NP-complete problems, in: Proc. 6th ACM Sympos. Theory of Computing, 1974, 47 – 63.

    Google Scholar 

  42. P. Gerl, Random walks on graphs with a strong isoperimetric property, J. Theoret. Probab. 1 (1988), 171–188.

    Article  MathSciNet  MATH  Google Scholar 

  43. P. Gerl, Amenable groups and amenable graphs, in: Harmonic Analysis (P. Eymard and J.-P. Pier, eds.), Lecture Notes in Math. 1359, Springer-Verlag, 1988, 181 – 190.

    Google Scholar 

  44. M. X. Goemans, D. P. Williamson, Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, J. Assoc. Comput. Mach. 42 (1995), 1115 – 1145.

    Article  MathSciNet  MATH  Google Scholar 

  45. C. D. Godsil, Algebraic Combinatorics, Chapman and Hall, New York, 1993.

    MATH  Google Scholar 

  46. M. Grötschel, L. Lovâsz, A. Schrijver, Geometric Algorithms and Combinatorial Optimization, Springer-Verlag, Berlin, 1988.

    Book  MATH  Google Scholar 

  47. L. Hagen, A. B. Kahng, New spectral methods for ratio cut partitioning and clustering, IEEE Trans. Comput.-Aided Design 11 (1992), 1074 – 1085.

    Article  Google Scholar 

  48. C. Helmberg, B. Mohar, S. Poljak, F. Rendl, A spectral approach to bandwidth and separator problems in graphs, Linear and Multilinear Algebra 39 (1995), 73 – 90.

    Article  MathSciNet  MATH  Google Scholar 

  49. C. Hendré, P. Tetali, Isoperimetric invariants for product Markov chains and graph products, submitted to Ann. Appl. Probab., 1996.

    Google Scholar 

  50. B. Hendrickson, R. Leland, An improved spectral graph partitioning algorithm for mapping parallel computations, SIAM J. Sci. Comput. 16 (1995), 452 – 469.

    Article  MathSciNet  MATH  Google Scholar 

  51. He] M.-C. Heydemann, Cayley graphs and interconnection networks, this volume

    Google Scholar 

  52. M.-C. Heydemann, J.-C. Meyer, D. Sotteau, On forwarding indices of networks, Discrete Appl. Math. 23 (1989), 103 – 123.

    Article  MathSciNet  MATH  Google Scholar 

  53. A. J. Hoffman, On eigenvalues and colorings of graphs, in: Graph Theory and Its Applications ( B. Harris, ed.), Academic Press, New York, 1970, 79 – 91.

    Google Scholar 

  54. M. Jerrum, A. Sinclair, Approximating the permanent, SIAM J. Comput. 18 (1989), 1149 – 1178.

    Article  MathSciNet  MATH  Google Scholar 

  55. F. Juhâsz, On a method of cluster analysis, Z. Angew. Math. Mech. 64 (1984), 335 – 336.

    MathSciNet  Google Scholar 

  56. M. Juvan, B. Mohar, Optimal linear labelings and eigenvalues of graphs, Discrete Appl. Math. 36 (1992), 153 – 168.

    Article  MathSciNet  MATH  Google Scholar 

  57. M. Juvan, B. Mohar, Laplace eigenvalues and bandwidth-type invariants of graphs, J. Graph Theory 17 (1993), 393 – 407.

    Article  MathSciNet  MATH  Google Scholar 

  58. R. Kannan, Markov chains and polynomial time algorithms, Proc. 35th Ann. Sympos. FOCS, 1994, 656 – 671.

    Google Scholar 

  59. D. Karger, R. Motwani, M. Sudan, Approximate graph coloring by semidefinite programming, Proc. 35th Ann. Sympos. FOCS, 1994, 2 – 13.

    Google Scholar 

  60. N. Karmarkar, A new polynomial-time algorithm for linear programming, Combinatorica 4 (1984), 373 – 395.

    Article  MathSciNet  MATH  Google Scholar 

  61. R. M. Karp, Reducibility among combinatorial problems, in: Complexity of Computer Computation ( R. E. Miller and J. W. Thather, eds.), Plenum Press, New York, 1972, 85 – 103.

    Chapter  Google Scholar 

  62. T. Kato, Perturbation Theory for Linear Operators, Springer-Verlag, Berlin, 1966.

    MATH  Google Scholar 

  63. L. G. Khachiyan, A polynomial algorithm in linear programming, Soviet. Math. Dokl. 20 (1979), 191 – 194.

    MATH  Google Scholar 

  64. G. Kirchhoff, Ü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 (1847), 497–508. Translated by J. B. O’Toole in I.R.E. Trans. Circuit Theory 5 (1958), 4.

    Google Scholar 

  65. Kn] D. E. Knuth, The sandwich theorem, Electron. J. Combin. 1 (1994), A#1.

    Google Scholar 

  66. L. Lovâsz, On the Shannon capacity of a graph, IEEE Trans. Inform. Theory 25 (1979), 1 – 7.

    Article  MathSciNet  MATH  Google Scholar 

  67. L. Lovâsz, M. Simonovits, The mixing rate of Markov chains, an isoperimetric inequality, and computing the volume, 31st Ann. Sympos. FOCS, 1990, 346 – 354.

    Google Scholar 

  68. L. Lovâsz, M. Simonovits, Random walks in a convex body and an improved volume algorithm, Random Structures Algorithms 4 (1993), 359 – 412.

    Article  MathSciNet  MATH  Google Scholar 

  69. A. Lubotzky, Discrete Groups, Expanding Graphs and Invariant Measures, Birkhäuser, Basel, 1994.

    Google Scholar 

  70. B. Mohar, Isoperimetric inequalities, growth, and the spectrum of graphs, Linear Algebra Appl. 103 (1988), 119 – 131.

    Article  MathSciNet  MATH  Google Scholar 

  71. B. Mohar, Isoperimetric numbers of graphs, J. Combin. Theory Ser. B 47 (1989), 274 – 291.

    Article  MathSciNet  MATH  Google Scholar 

  72. B. Mohar, The Laplacian spectrum of graphs, in: Graph Theory, Combinatorics, and Applications, ( Y. Alavi et al., eds.), Wiley, New York, 1991, 871 – 898.

    Google Scholar 

  73. B. Mohar, Some relations between analytic and geometric properties of infinite graphs, Discrete Math. 95 (1991), 193 – 219.

    Article  MathSciNet  MATH  Google Scholar 

  74. B. Mohar, S. Poljak, Eigenvalues and the max-cut problem, Czechoslovak Math. J. 40 (115) (1990), 343–352.

    MathSciNet  Google Scholar 

  75. B. Mohar, S. Poljak, Eigenvalues in combinatorial optimization, in: Combinatorial and Graph-Theoretical Problems in Linear Algebra (R. A. Brualdi, S. Friedland, V. Klee, eds.), IMA Vol. Math. Appl. 50, Springer-Verlag, 1993, 107 – 151.

    Google Scholar 

  76. B. Mohar, W. Woess, A survey on spectra of infinite graphs, Bull. London Math. Soc. 21 (1989), 209 – 234.

    Article  MathSciNet  MATH  Google Scholar 

  77. R. Motwani, P. Raghavan, Randomized Algorithms, Cambridge University Press, New York, 1995

    MATH  Google Scholar 

  78. Yu. Nesterov, A. Nemirovskii, Self-Concordant Functions and Polynomial Time Methods in Convex Programming, Central Economic and Mathematical Institute, USSR Academy of Science, Moscow, 1989.

    Google Scholar 

  79. Yu. Nesterov, A. Nemirovskii, Interior Point Polynomial Methods in Convex Programming, SIAM, Philadelphia, PA, 1994.

    Google Scholar 

  80. C. H. Papadimitriou, M. Yannakakis, Optimization, approximation, and complexity classes, J. Comput. System. Sci. 43 (1991), 425 – 440.

    Article  MathSciNet  MATH  Google Scholar 

  81. A. L. T. Paterson, Amenability, Math. Surveys Monographs 29, Amer. Math. Soc., Providence, RI, 1988.

    Google Scholar 

  82. J.-P. Pier, Amenable Locally Compact Groups, Wiley, New York, 1984.

    Google Scholar 

  83. S. Poljak, F. Rendl, Nonpolyhedral relaxations of graph-bisection problems, SIAM J. Optim. 5 (1995), 467 – 487.

    Article  MathSciNet  MATH  Google Scholar 

  84. A. Pothen, H. D. Simon, L. Wang, Spectral nested dissection, preprint, 1992.

    Google Scholar 

  85. F. Rendl, H. Wolkowicz, Applications of parametric programming and eigenvalue maximization to the quadratic assignment problem, Math. Programming 53 (1992), 63 – 78.

    Article  MathSciNet  MATH  Google Scholar 

  86. J. M. Rosenblatt, Invariant measures and growth conditions, Trans. Amer. Math. Soc. 193 (1974), 33 – 53.

    Article  MathSciNet  MATH  Google Scholar 

  87. J. S. Rosenthal, Convergence rates for Markov chains, SIAM Rev. 37 (1995), 387 – 405.

    Article  MathSciNet  MATH  Google Scholar 

  88. H. D. Simon, Partitioning of unstructured problems for parallel processing, Comput. Syst. in Engin. 2 (1991), 135 – 148.

    Article  Google Scholar 

  89. A. Sinclair, Algorithms for Random Generation and Counting: A Markov Chain Approach, Birkhäuser, Boston, 1993.

    Google Scholar 

  90. A. J. Sinclair, M. R. Jerrum, Approximate counting, uniform generation and rapidly mixing Markov chains, Inform. and Comput. 82 (1989), 93 – 133.

    Article  MathSciNet  MATH  Google Scholar 

  91. P. M. Soardi, W. Woess, Amenability, unimodularity, and the spectral radius of random walks on infinite graphs, Math. Z. 205 (1990), 471 – 486.

    Article  MathSciNet  MATH  Google Scholar 

  92. P. Solé, Expanding and forwarding, Discrete Appl. Math. 58 (1995), 67 – 78.

    Article  MathSciNet  MATH  Google Scholar 

  93. D. A. Spielman, S.-H. Teng, Spectral partitioning works: Planar graphs and finite element meshes, preprint, 1996.

    Google Scholar 

  94. C. Thomassen, Trees, ends, and transience, in: Harmonic Analysis and Discrete Potential Theory (Frascati 1991) ( M. A. Picardello, ed.) Plenum, New York, 1992, 259 – 266.

    Google Scholar 

  95. J. G. Stampfli, Compact perturbations, normal eigenvalues, and a problem of Salinas, J. London Math. Soc. 9 (1974), 165 – 175.

    Article  MathSciNet  MATH  Google Scholar 

  96. P. M. Vaidya, A new algorithm for minimizing convex functions over convex sets, Proc. 30th Ann. Sympos. FOCS, 1989, 338 – 343.

    Google Scholar 

  97. L. G. Valiant, The complexity of computing the permanent, Theoret. Comput. Sci. 8 (1979), 189 – 201.

    Article  MathSciNet  MATH  Google Scholar 

  98. N. T. Varopoulos, Isoperimetric inequalities and Markov chains, J. Funct. Anal. 63 (1985), 215 – 239.

    Article  MathSciNet  MATH  Google Scholar 

  99. H. S. Wilf, The eigenvalues of a graph and its chromatic number, J. London Math. Soc. 42 (1967), 330 – 332.

    Article  MathSciNet  MATH  Google Scholar 

  100. R. D. Williams, Performance of dynamic load balancing algorithms for unstructured mesh calculations, Technical Report, California Inst. of Technology, 1990.

    Google Scholar 

  101. W. Woess, Random walks on infinite graphs and groups - A survey on selected topics, Bull. London Math. Soc. 26 (1994), 1 – 60.

    Article  MathSciNet  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Mathematics, University of Ljubljana, Jadranska 19, 1111, Ljubljana, Slovenia

    Bojan Mohar

Authors
  1. Bojan Mohar
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Départment d’Informatique et de Recherche opérationnelle, Université de Montréal, CP 6128, Succ. Centre-ville, H3C 3J7, Montréal, Québec, Canada

    Geňa Hahn

  2. Départment de Mathématiques et de Statistique, Université de Montréal, CP 6128, Succ. Centre-ville, H3C 3J7, Montréal, Québec, Canada

    Gert Sabidussi

Rights and permissions

Reprints and permissions

Copyright information

© 1997 Springer Science+Business Media Dordrecht

About this chapter

Cite this chapter

Mohar, B. (1997). Some applications of Laplace eigenvalues of graphs. In: Hahn, G., Sabidussi, G. (eds) Graph Symmetry. NATO ASI Series, vol 497. Springer, Dordrecht. https://doi.org/10.1007/978-94-015-8937-6_6

Download citation

  • DOI: https://doi.org/10.1007/978-94-015-8937-6_6

  • Publisher Name: Springer, Dordrecht

  • Print ISBN: 978-90-481-4885-1

  • Online ISBN: 978-94-015-8937-6

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation