Eigenvalues and the max-cut problem

Bojan Mohar; Svatopluk Poljak

Czechoslovak Mathematical Journal (1990)

  • Volume: 40, Issue: 2, page 343-352
  • ISSN: 0011-4642

How to cite

top

Mohar, Bojan, and Poljak, Svatopluk. "Eigenvalues and the max-cut problem." Czechoslovak Mathematical Journal 40.2 (1990): 343-352. <http://eudml.org/doc/13856>.

@article{Mohar1990,
author = {Mohar, Bojan, Poljak, Svatopluk},
journal = {Czechoslovak Mathematical Journal},
keywords = {max-cut problem; Laplacian eigenvalues; Kneser graphs; circulants; Ramanujan graphs},
language = {eng},
number = {2},
pages = {343-352},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {Eigenvalues and the max-cut problem},
url = {http://eudml.org/doc/13856},
volume = {40},
year = {1990},
}

TY - JOUR
AU - Mohar, Bojan
AU - Poljak, Svatopluk
TI - Eigenvalues and the max-cut problem
JO - Czechoslovak Mathematical Journal
PY - 1990
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 40
IS - 2
SP - 343
EP - 352
LA - eng
KW - max-cut problem; Laplacian eigenvalues; Kneser graphs; circulants; Ramanujan graphs
UR - http://eudml.org/doc/13856
ER -

References

top
  1. N. Alon, 10.1007/BF02579166, Combinatorica 6, (1986) 83-96. (1986) Zbl0661.05053MR0875835DOI10.1007/BF02579166
  2. N. Alon V. D. Milman, 10.1016/0095-8956(85)90092-9, J. Comb. Th. B 38 (1985) 73-88. (1985) MR0782626DOI10.1016/0095-8956(85)90092-9
  3. W. N. Anderson T. D. Morley, 10.1080/03081088508817681, Lin. Multilin. Algebra 18 (1985) 141-145. (1985) MR0817657DOI10.1080/03081088508817681
  4. F. Barahona, 10.1016/0167-6377(83)90016-0, Oper. Res. Lett. 2 (1983) 107-111. (1983) MR0717742DOI10.1016/0167-6377(83)90016-0
  5. F. Barahona M. Grötschel M. Jünger G. Reinelt, 10.1287/opre.36.3.493, Oper. Res. 36 (1988) 493-513. (1988) DOI10.1287/opre.36.3.493
  6. D. M. Cvetkovic M. Doob, and H. Sachs, Spectra of graphs - Theory and applications, VEB Deutscher Verlag der Wiss. Berlin 1979/Acad. Press, N.Y. 1979. (1979) 
  7. M. Fiedler, Algebraic connectivity of graphs, Czechoslovak Math. J. 23 (98) (1973) 298-305. (1973) Zbl0265.05119MR0318007
  8. M. Grötschel, G. L. Nemhauser, 10.1007/BF02591727, Math. Programming 29 (1984) 28-40. (1984) MR0740503DOI10.1007/BF02591727
  9. M. Grötschel, W. R. Pulleyblank, 10.1016/0167-6377(81)90020-1, Oper. Res.Lett. / (1981) 23-27. (1981) MR0643056DOI10.1016/0167-6377(81)90020-1
  10. F. Hadlock, 10.1137/0204019, SIAM J. on Comp. 4 (1975) 221-225. (1975) Zbl0321.05120MR0379290DOI10.1137/0204019
  11. R. M. Karp, Reducibility among combinatorial problems, in Complexity of Computer Computations, R. E. Miller, J. W. Thatcher (eds.), Plenum Press, New York 1972, pp. 85-103. (1972) MR0378476
  12. A. K. Kel'mans, Properties of the characteristic polynomial of a graph, "Kibernetiky - na službu kommunizmu" vol. 4, Energija, Moskva-Leningrad, 1967, pp. 27-41 (in Russian). (1967) MR0392633
  13. P. Lankaster, Theory of Matrices, Acad. Press, New York-London 1969. (1969) MR0245579
  14. L. Lovász, 10.1109/TIT.1979.1055985, IEEE Trans. Inform. Theory 25 (1979) 1-7. (1979) MR0514926DOI10.1109/TIT.1979.1055985
  15. A. Lubotzky R. Phillips, P. Sarnak, 10.1007/BF02126799, Combinatorica, 8 (1988) 261-277. (1988) MR0963118DOI10.1007/BF02126799
  16. B. Mohar, Isoperimetric numbers of graphs, J. Comb. Th. B, to appear. Zbl0719.05042MR1026065
  17. B. Mohar, The Laplacian spectrum of graphs, submitted. Zbl0840.05059
  18. J. Nešetřil, S. Poljak, 10.1016/0167-6377(86)90031-3, Oper. Res. Lett. 4 (1986) 289-291. (1986) MR0836264DOI10.1016/0167-6377(86)90031-3
  19. G. I. Orlova, Y. G. Dorfman, Finding the maximal cut in a graph, Engrg. Cybernetics 10 (1972) 502-506. (1972) MR0329962
  20. S. Poljak, Z. Tuza, 10.1007/BF01788540, Graphs and Combinatorics, 3 (1987) 191-199. (1987) Zbl0674.05064MR0932133DOI10.1007/BF01788540
  21. S. Poljak, D. Turzík, 10.1016/0012-365X(86)90192-5, Discrete Math. 58 (1986) 99-104. (1986) MR0820844DOI10.1016/0012-365X(86)90192-5
  22. S. Poljak, D. Turzík, Maximum bipartite subgraphs of circulants, submitted. 
  23. R. M. Tanner, 10.1137/0605030, SIAM J. Alg. Disc. Meth. 5 (1984) 287-293. (1984) Zbl0554.05045MR0752035DOI10.1137/0605030

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.