Extremal Graph Realizations and Graph Laplacian Eigenvalues
From MaRDI portal
Abstract: For a regular polyhedron (or polygon) centered at the origin, the coordinates of the vertices are eigenvectors of the graph Laplacian for the skeleton of that polyhedron (or polygon) associated with the first (non-trivial) eigenvalue. In this paper, we generalize this relationship. For a given graph, we study the eigenvalue optimization problem of maximizing the first (non-trivial) eigenvalue of the graph Laplacian over non-negative edge weights. We show that the spectral realization of the graph using the eigenvectors corresponding to the solution of this problem, under certain assumptions, is a centered, unit-distance graph realization that has maximal total variance. This result gives a new method for generating unit-distance graph realizations and is based on convex duality. A drawback of this method is that the dimension of the realization is given by the multiplicity of the extremal eigenvalue, which is typically unknown prior to solving the eigenvalue optimization problem. Our results are illustrated with a number of examples.
Recommendations
- On extremal eigenvalues of the graph Laplacian *
- Graph realizations associated with minimizing the maximum eigenvalue of the Laplacian
- Eigenvalues and extremal degrees of graphs
- Characterization of extremal graphs from Laplacian eigenvalues and the sum of powers of the Laplacian eigenvalues of graphs
- Bounding the gap between extremal Laplacian eigenvalues of graphs
- On the extensional eigenvalues of graphs
- Bounds for the extreme eigenvalues of the Laplacian and signless Laplacian of a graph
- Extrema of graph eigenvalues
- Extreme eigenvalues of nonregular graphs
- Characterization of extremal graphs from distance signless Laplacian eigenvalues
Cites work
- Computation of free boundary minimal surfaces via extremal Steklov eigenvalue problems
- CVXPY: a Python-embedded modeling language for convex optimization
- Distance-regular graphs
- Eigenvalue multiplicities of highly symmetric graphs
- Eigenvalues of the Laplacian of a graph∗
- Eigenvectors of Distance-Regular Graphs
- Existence and regularity of maximal metrics for the first Laplace eigenvalue on surfaces
- scientific article; zbMATH DE number 3634287 (Why is no real title available?)
- scientific article; zbMATH DE number 2107836 (Why is no real title available?)
- scientific article; zbMATH DE number 867649 (Why is no real title available?)
- scientific article; zbMATH DE number 3417498 (Why is no real title available?)
- Laplacian eigenvectors of graphs. Perron-Frobenius and Faber-Krahn type theorems
- Optimal data collection for informative rankings expose well-connected graphs
- Sharp eigenvalue bounds and minimal surfaces in the ball
- Spectrally optimized pointset configurations
- Upper bounds on algebraic connectivity via convex optimization
Cited in
(9)- Extremal properties of eigenvalues for a metric graph.
- Graphs with few distinct eigenvalues and extremal energy
- Extremal eigenvalues of critical Erdős-Rényi graphs
- Spectral extrema for graphs: the Zarankiewicz problem
- Embedding and the first Laplace eigenvalue of a finite graph
- Graph realizations associated with minimizing the maximum eigenvalue of the Laplacian
- Extremal norms of graphs and matrices
- Ellipsoidal embeddings of graphs
- Extreme eigenvalues of nonregular graphs
This page was built for publication: Extremal Graph Realizations and Graph Laplacian Eigenvalues
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6171259)
