Maximization of the first Laplace eigenvalue of a finite graph
In this paper, the authors study extremal solutions of a first-Laplacian-eigenvalue maximization problem on weighted graphs first proposed by \textit{K. Fujiwara} [Proc. Am. Math. Soc. 123, No. 8, 2585--2594 (1995; Zbl 0833.58039)]. Let \(G = (V, E)\) be a finite graph. Let \(\ell: E \rightarrow \mathbb{R}_{>0}\) be an edge-length function. From the edge-length function \(\ell\), define a vertex-weight \(m_0 : V\rightarrow \mathbb{R}_0\) by \(m_0(u) = \sum_{v\sim u}\ell(uv)\) for \(u\in V\), and an edge-weight \(m_1 : E\rightarrow \mathbb{R}_{>0}\) by \(m_1(uv) = \dfrac{1}{\ell(uv)}\) for \(uv \in E\). The graph Laplacian is then the positive symmetric linear operator \(\Delta_{\ell}:\mathbb{R}^V \rightarrow \mathbb{R}^V\) given by \[ (\Delta_{\ell}\varphi)(u) = \sum_{v\sim u}\frac{m_1(uv)}{m_0(u)}(\varphi(u) - \varphi(v)), \quad u\in V, \] where \(\mathbb{R}^V\) is the set of functions \(\varphi: V\rightarrow \mathbb{R}\). Fujiwara's maximization problem is the following: maximize the first nonzero eigenvalue \(\lambda_1(G, \ell)\) of the graph Laplacian \(\Delta_{\ell}\) over all edge-length functions \(\ell\) subject to the normalization \(\sum_{u\in V}m_0(u) = 2\sum_{uv\in E}\ell(uv) = 1\). The main result of this paper is that any extremal solution of Fujiwara's maximization problem admits an explicit description in terms of eigenfunctions of the eigenvalue \(\lambda_1(G, \ell)\). Namely, if \(\ell\) is an extremal solution of Fujiwara's maximization problem, then there exist eigenfunctions \(\varphi_1, \ldots, \varphi_N\) of the eigenvalue \(\lambda_1(G, \ell)\) of \(\Delta_{\ell}\) such that the map \(\varphi = (\varphi_1, \ldots, \varphi_N) : V \rightarrow \mathbb{R}^N\) satisfies \[ \ell(uv)^2 = \frac{|\varphi(u) - \varphi(v)|^2}{1 - \lambda_1(G, \ell)(|\varphi(u)|^2 + |\varphi(v)|^2)}, \] for all \(uv \in E\). This result is a graph analogue of a result of \textit{N. Nadirashvili} [Geom. Funct. Anal. 6, No. 5, 877--897 (1996; Zbl 0868.58079)] about extremal solutions of the problem of maximizing the first Laplacian eigenvalue associated with a Riemannian metric on a compact surface. The authors illustrate their result by finding extremal solutions to the Fujiwara maximization problem on several graphs with three or four vertices. They also use their method to reprove a result of \textit{F. Göring} et al. [SIAM J. Optim. 19, No. 1, 472--501 (2008; Zbl 1169.05347)] on a different first-Laplacian-eigenvalue maximization problem.
- A new conformal invariant and its applications to the Willmore conjecture and the first eigenvalue of compact surfaces
- Absolute algebraic connectivity of trees
- Berger's isoperimetric problem and minimal immersions of surfaces
- Eigenvalues of Laplacians on a Closed Riemannian Manifold and Its Nets
- Embedded in the Shadow of the Separator
- Existence and regularity of maximal metrics for the first Laplace eigenvalue on surfaces
- Expander graphs and their applications
- How large can the first eigenvalue be on a surface of genus two?
- scientific article; zbMATH DE number 3698075 (Why is no real title available?)
- scientific article; zbMATH DE number 3356292 (Why is no real title available?)
- scientific article; zbMATH DE number 3406793 (Why is no real title available?)
- scientific article; zbMATH DE number 964896 (Why is no real title available?)
- Metrics on a closed surface of genus two which maximize the first eigenvalue of the Laplacian
- Minimal immersions of surfaces by the first eigenfunctions and conformal area
- On the first eigenvalue of the Laplacian on compact surfaces of genus three
- On the least positive eigenvalue of the Laplacian for compact group manifolds
- Riemannian manifolds admitting isometric immersions by their first eigenfunctions
- Riemannian Metrics with Large λ 1
- Sharp asymptotics of the first eigenvalue on some degenerating surfaces
- The first eigenvalue of the Laplacian on orientable surfaces
- The geometry of graphs and some of its algorithmic applications
- The rotational dimension of a graph
This page was built for publication: Maximization of the first Laplace eigenvalue of a finite graph
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6973054)