scientific article; zbMATH DE number 4193718

zbMath0724.05046MaRDI QIDQ5202209

Bojan Mohar, Svatopluk Poljak

Publication date: 1990

Full work available at URL: https://eudml.org/doc/13856

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

Laplacian eigenvaluesmax-cut problemcirculantsKneser graphsRamanujan graphs

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50)

Related Items

Max \(k\)-cut and the smallest eigenvalue, Automated conjectures on upper bounds for the largest Laplacian eigenvalue of graphs, Inverse Perron values and connectivity of a uniform hypergraph, Mathematical Programming Models and Exact Algorithms, Solving the max-cut problem using eigenvalues, A projection technique for partitioning the nodes of a graph, Old and new results on algebraic connectivity of graphs, Large cuts with local algorithms on triangle-free graphs, A class of spectral bounds for max \(k\)-cut, Tighter spectral bounds for the cut size, based on Laplacian eigenvectors, New bounds for the \(\max\)-\(k\)-cut and chromatic number of a graph, New results for MaxCut in H$H$‐free graphs, Graph realizations associated with minimizing the maximum eigenvalue of the Laplacian, On graphs with adjacency and signless Laplacian matrices eigenvectors entries in \(\{-1,+1\}\), Max-cut and extendability of matchings in distance-regular graphs, Laplace eigenvalues of graphs---a survey, The performance of an eigenvalue bound on the max-cut problem in some classes of graphs, A survey of automated conjectures in spectral graph theory, Spectral bounds for unconstrained \((- 1,1)\)-quadratic optimization problems, The Laplacian spectral radius of a graph under perturbation, Checking robust nonsingularity is NP-hard, Spectral bounds for the maximum cut problem, Laplacian eigenvalues and partition problems in hypergraphs, Solving quadratic (0,1)-problems by semidefinite programs and cutting planes, Bounds for the Laplacian spectral radius of graphs, Some minimax problems for graphs, The product of two high-frequency graph Laplacian eigenfunctions is smooth, Laplacian eigenvalues and the maximum cut problem, Node and edge relaxations of the max-cut problem, Laplacian matrices of graphs: A survey

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The max-cut problem on graphs not contractible to \(K_ 5\)
• \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators
• A polynomial time heuristic for certain subgraph optimization problems with guaranteed worst case bound
• A remark on max-cut problem with an application to digital-analogue convertors
• Ramanujan graphs
• Eigenvalues and expanders
• Maximum bipartite subgraphs of Kneser graphs
• Weakly bipartite graphs and the max-cut problem
• Isoperimetric numbers of graphs
• Explicit Concentrators from Generalized N-Gons
• A polynomial algorithm for the max-cut problem on graphs without long odd cycles
• Eigenvalues of the Laplacian of a graph^∗
• An Application of Combinatorial Optimization to Statistical Physics and Circuit Layout Design
• Finding a Maximum Cut of a Planar Graph in Polynomial Time
• On the Shannon capacity of a graph