Maximization of the first Laplace eigenvalue of a finite graph

From MaRDI portal





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.



Cites work









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)