Maximization of the first Laplace eigenvalue of a finite graph (Q6973054)

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\N\[\N(\Delta_{\ell}\varphi)(u) = \sum_{v\sim u}\frac{m_1(uv)}{m_0(u)}(\varphi(u) - \varphi(v)), \quad u\in V,\N\]\Nwhere \(\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\).\N\NThe 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\N\[\N\ell(uv)^2 = \frac{|\varphi(u) - \varphi(v)|^2}{1 - \lambda_1(G, \ell)(|\varphi(u)|^2 + |\varphi(v)|^2)},\N\]\Nfor 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.\N\NThe 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.