Laplace eigenvalues of graphs—a survey
Discrete MathematicsPublished 1 November 1992
Bojan Mohar
Citations229
SJR quartileQ1
SJR score0.88
SNIP1.18
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
Several applications of Laplace eigenvalues of graphs in graph theory and combinatorial optimization are outlined.
Abstract
Several applications of Laplace eigenvalues of graphs in graph theory and combinatorial optimization are outlined.
Keywords
Computer ScienceMathematics
Distance-Regular Graphs
2,112 Citations1989Andries E. Brouwer, Arjeh M. Cohen +1 more
Spectra of graphs : theory and application
1,831 Citations1995Dragoš Cvetković, Michael Doob +1 more
SIAM Journal on Matrix Analysis and ApplicationsPartitioning Sparse Matrices with Eigenvectors of Graphs
1,692 Citations1990Alex Pothen, Horst D. Simon +1 more
It is shown that lower bounds on separator sizes can be obtained in terms of the eigenvalues of the Laplacian matrix associated with a graph, which can be used to compute good separators in grid graphs.
IEEE Transactions on Information TheoryOn the Shannon capacity of a graph
1,658 Citations1979László Lovász
It is proved that the Shannon zero-error capacity of the pentagon is \sqrt{5} and a well-characterized, and in a sense easily computable, function is introduced which bounds the capacity from above and equals the capacity in a large number of cases.
Handbook of Combinatorics
1,523 Citations1995Ronald Graham, Martin Grötschel +1 more
COMBINATORICAEigenvalues and expanders
1,170 Citations1986Noga Alon
It is shown that a regular bipartite graph is an expanderif and only if the second largest eigenvalue of its adjacency matrix is well separated from the first.
THE LAPLACIAN SPECTRUM OF GRAPHS y
1,118 Citations1991Bojan Mohar
COMBINATORICARamanujan graphs
1,003 Citations1988Alexander Lubotzky, Ralph S. Phillips +1 more
The girth ofX is asymptotically ≧4/3 logk−1 ¦X¦ which gives larger girth than was previously known by explicit or non-explicit constructions.
The Annals of Applied ProbabilityGeometric Bounds for Eigenvalues of Markov Chains
886 Citations1991Persi Diaconis, Daniel W. Stroock
Journal of Combinatorial Theory Series Bλ1, Isoperimetric inequalities for graphs, and superconcentrators
866 Citations1985Noga Alon, Vitali Milman
Information and ComputationApproximate counting, uniform generation and rapidly mixing Markov chains
757 Citations1989Alistair Sinclair, Mark Jerrum
Journal of the ACMA random polynomial-time algorithm for approximating the volume of convex bodies
701 Citations1991Martin Dyer, Alan Frieze +1 more
The proof of correctness of the algorithm relies on recent theory of rapidly mixing Markov chains and isoperimetric inequalities to show that a certain random walk can be used to sample nearly uniformly from within K within Euclidean space.
COMBINATORICAThe eigenvalues of random symmetric matrices
673 Citations1981Zoltán Füredi, János Komlós
It is shown that with probability 1-o(1)all eigenvalues belong to the above intervalI if μ=0, while in case μ>0 only the largest eigenvalueλ1 is outsideI, and λ1 asymptotically has a normal distribution with expectation (n−1)μ+v+(σ2/μ) and variance 2σ2 (bounded variance!).
SIAM Journal on Matrix Analysis and ApplicationsThe Laplacian Spectrum of a Graph
544 Citations1990Robert Grone, Russell Merris +1 more
Communications in Mathematical PhysicsTheory of monomer-dimer systems
510 Citations1972Ole J. Heilmann, Élliott H. Lieb
Communications in Mathematical PhysicsTheory of monomer-dimer systems
409 Citations1972Ole J. Heilmann, Élliott H. Lieb
Journal of Combinatorial Theory Series BIsoperimetric numbers of graphs
333 Citations1989Bojan Mohar
The upper bound is a strong discrete version of the wellknown Cheeger inequality bounding the first eigenvalue of a Riemannian manifold.
Eigenvalues and graph bisection: An average-case analysis
323 Citations1987Ravi B. Boppana
This paper presents an algorithm that will, for almost all graphs in a certain class, output the minimum-size bisection and will yield a proof that the bisection is optimal.
Graphs and CombinatoricsEigenvalues, diameter, and mean distance in graphs
299 Citations1991Bojan Mohar
Upper and lower bounds on the diameter and the mean distance inG in terms ofλ2, the second smallest eigenvalue of the difference Laplacian matrix of a graphG, are derived.
On the second eigenvalue of random regular graphs
222 Citations1989Joel Friedman, J. Kahn +1 more
The following is an extended abstract for two papers, one written by Kahn and Szemeredi, the other written by Friedman, which have been combined at the request of the STOC committee.
The mixing rate of Markov chains, an isoperimetric inequality, and computing the volume
198 Citations2002László Lovász, Miklós Simonovits
The authors generalize a bound on the mixing rate of time-reversible Markov chains in terms of their conductance by not assuming time reversibility and using a weaker notion of conductance and prove an isoperimetric inequality for subsets of a convex body.
Mathematical ProgrammingLaplacian eigenvalues and the maximum cut problem
186 Citations1993Charles Delorme, S. Poljak
An eigenvalue upper boundϕ(G) on the maximum cut mc (G) of a weighted graph has several interesting properties that resemble the behaviour ofmc (G), and ϕ is subadditive with respect to amalgam, and additive withrespect to disjoint sum and 1-sum.
Discrete Applied MathematicsOptimal linear labelings and eigenvalues of graphs
140 Citations1992Martin Juvan, Bojan Mohar
For several NP-hard optimal linear labeling problems, including the bandwidth, the cutwidth, and the min-sum problem for graphs, a heuristic algorithm is proposed which finds approximative solutions to these problems in polynomial time.
The IMA volumes in mathematics and its applicationsEigenvalues in Combinatorial Optimization
133 Citations1993Bojan Mohar, Svatopluk Poljak
In the last decade many important applications of eigenvalues and eigenvectors of graphs in combinatorial optimization were discovered.
Random Structures and AlgorithmsMaximum hitting time for random walks on graphs
126 Citations1990Graham Brightwell, Peter Winkler
For x and y vertices of a connected graph G, let TG(x, y) denote the expected time before a random walk starting from x reaches y, and it is determined that for each n > 0, the n‐vertex graph G and verticesx and y for whichTG(x) is maximized.
Mathematics of Operations ResearchA New Lower Bound Via Projection for the Quadratic Assignment Problem
122 Citations1992Scott Hadley, Franz Rendl +1 more
New lower bounds for the quadratic assignment problem QAP are presented, based on the orthogonal relaxation of QAP, and an additional improvement is obtained by making efficient use of a tractable representation of Orthogonal matrices having constant row and column sums.
Journal of Theoretical ProbabilityBounds on the cover time
117 Citations1989Andrei Broder, Anna R. Karlin
Journal of Theoretical ProbabilityOn the cover time of random walks on graphs
114 Citations1989Jeff D. Kahn, Nathan Linial +2 more
Bulletin of the American Mathematical SocietyRamanujan graphs and Hecke operators
113 Citations1990Arnold Pizer
On the second eigenvalue of random regular graphs
103 Citations1987Andrei Broder, Eli Shamir
It is shown that the second eigenvalue of d-regular graphs, λ2, is concentrated in an interval of width O(√d) around its mean, and that its mean is O(d3/4) under various models for random d-regular graphs.
Random Structures and AlgorithmsQuasi‐random hypergraphs
103 Citations1990Fan Chung, R. L. Graham
A large equivalence class of properties shared by most hypergraphs, including so-called random hyper graphs, are described, which shows that many global properties of hyperGraphs are actually consequences of simple local conditions.
Combinatorial theory and statistical design
87 Citations1987Gregory M. Constantine
Journal of Combinatorial Theory Series BMaximizing the total number of spanning trees in a graph: Two related problems in graph theory and optimum design theory
86 Citations1981Ching‐Shui Cheng
A regular complete multipartite graph is shown to have the maximum number of spanning trees among all the simple graphs with the same numbers of vertices and edges.
COMBINATORICACubic Ramanujan graphs
85 Citations1992Patrick Chiu
A fimily of cubic Ramanujan graph is explicitly constructed and this graph is realized as Cayley graphs of a certain free group acting on the 3-regular tree.
Journal of Theoretical ProbabilityLower bounds for covering times for reversible Markov chains and random walks on graphs
83 Citations1989David Aldous
For simple random walk on aN-vertex graph, the mean time to cover all vertices is at leastcN log(N), wherec>0 is an absolute constant, deduced from a more general result about stationary finite-state reversible Markov chains.
Probability Theory and Related FieldsOn the time taken by random walks on finite groups to visit every state
82 Citations1983David Aldous
Linear Algebra and its ApplicationsGraph partitioning by Eigenvectors
80 Citations1988David L. Powers
Mathematical ProgrammingApplications of parametric programming and eigenvalue maximization to the quadratic assignment problem
79 Citations1992Franz Rendl, Henry Wolkowicz
The lower bound found by using an eigenvalue decomposition of the quadratic part and by solving a linear program for the linear part is improved by applying a steepest ascent algorithm to the sum of the two bounds.
SIAM Journal on Discrete MathematicsCommunication Complexity and Quasi Randomness
74 Citations1993Fan Chung, Prasad Tetali
It is proved that the multiparty communication complexity problems are equivalent to certain hypergraph properties and thereby establish the connections among a large number of combinatorial and computational aspects of hypergraphs or Boolean functions.
Graphs and CombinatoricsOrdering trees by algebraic connectivity
74 Citations1990Robert Grone, Russell Merris
The authors explore a graph theoretic interpretation for the difference between a(T1) anda(T2), and calla(G) thealgebraic connectivity of G, the graph onn vertices that is positive semidefinite symmetric.
Random Structures and AlgorithmsQuasi‐random classes of hypergraphs
71 Citations1990Fan Chung
This work investigates the relations among a number of different graph properties for k-uniformhypergraphs, which are shared by random hypergraphs and form equivalence classes which constitute a natural hierarchy.
European Journal of CombinatoricsCombinatorial Properties and the Complexity of a Max-cut Approximation
62 Citations1993Charles Delorme, Svatopluk Poljak
It is shown that the bound behaves in a manner similar to the max-cut for the operations of switching, vertex splitting, contraction and decomposition, and it can be adjusted for branch and bound techniques.
Linear and Multilinear AlgebraAn edge version of the matrix-tree theorem and the wiener index
59 Citations1989Russell Merris
Mathematical Proceedings of the Cambridge Philosophical SocietyHitting times for random walks on vertex-transitive graphs
51 Citations1989David Aldous
European Journal of CombinatoricsDiameter, Covering Index, Covering Radius and Eigenvalues
50 Citations1991Charles Delorme, Patrick Solé
An upper bound on the covering radius of a code as a function of the scattering of the weights of the dual code is derived, which is tighter, for d?
Linear and Multilinear AlgebraAbsolute algebraic connectivity of trees
49 Citations1990Miroslav Fiedler
Discrete MathematicsThe performance of an eigenvalue bound on the max-cut problem in some classes of graphs
42 Citations1993Charles Delorme, S. Poljak
The performance of a number ?
Journal of Graph TheoryLaplace eigenvalues and bandwidth‐type invariants of graphs
40 Citations1993Martin Juvan, Bojan Mohar
For (weighted) graphs several labeling properties and their relation to the eigenvalues of the Laplacian matrix of a graph are considered and several upper and lower bounds on the bandwidth and other min-sum problems are derived.
COMBINATORICACounting colorful multi-dimensional trees
39 Citations1992Ron M. Adin
The Binet-Cauchy theorem is used to count thek-dimensional colorful trees onV (for allk), where each treeT is counted with weight $$|\tilde H_{k - 1} (\Delta _T )|^2 (Tilde H_* = reduced homology)$$ .
Linear and Multilinear AlgebraGraph complexity and the laplacian matrix in blocked experiments
34 Citations1990Gregory M. Constantine
Discrete Applied MathematicsA domain monotonicity theorem for graphs and Hamiltonicity
33 Citations1992Bojan Mohar
A necessary condition for the existence of long cycles in a graph involving the Laplacian spectrum of graphs is derived based on two theorems which relate the eigenvalues of a graph and the eigens of its induced subgraphs.
Linear Algebra and its ApplicationsBounds on expected hitting times for a random walk on a connected graph
25 Citations1990JoséLuis Palacios
Linear Algebra and its ApplicationsLower bounds for the first eigenvalue of certain M-matrices associated with graphs
19 Citations1992Shmuel Friedland
Linear and Multilinear AlgebraThe laplacian matrix of a graph: unimodular congruence
17 Citations1990William Watkins
Linear and Multilinear AlgebraLarge eigenvalues of the laplacian
16 Citations1990Robert Grone, Georg Zimmermann
Linear and Multilinear AlgebraCoalescence, majorization, edge valuations and the laplacian spectra of graphs
15 Citations1990Robert Grone, Russell Merris
Linear Algebra and its ApplicationsSymmetrization of nonsymmetric quadratic assignment problems and the Hoffman-Wielandt inequality
14 Citations1992Scott Hadley, Franz Rendl +1 more
Linear and Multilinear AlgebraA minimax problem for graphs and its relation to generalized doubly stochastic matrices
11 Citations1990Miroslav Fiedler
StatisticsOn the theoretical backgrounds of cluster analysis based on the eigenvalue problem of the association matrix
9 Citations1989Ferenc Juhász
Transactions of the American Mathematical SocietyCohomological Aspects of Hypergraphs
4 Citations1992Fan Chung, Ronald Graham