View PDF HTML (experimental)

Abstract:We study discrete analogues of classical spectral geometric inequalities and extremal eigenvalue problems on graphs. The well-known Krahn--Szegő inequality states that the minimum of $\lambda_2(\Omega)$ among bounded open sets of $\mathbb{R}^n$ with given volume is achieved by the union of two identical balls $\mathbb{R}^n$. Firstly, we establish a Krahn--Szegő type inequality for trees. For trees with a fixed number of interior vertices and boundary leaves, we completely characterize the extremal structures that minimize the second Dirichlet eigenvalue. Secondly, we develop a nodal domain method for adjacency matrices. By proving a nodal domain theorem in adjacency version for graphs, we obtain upper bounds for the second largest adjacency eigenvalue $\rho_2(G)$ of $G$ in given graph classes. These bounds imply some previous results. Finally, we settle the Aouchiche--Hansen conjecture (2010) on the second largest eigenvalue with given number of edges and clique number. We prove that for connected graphs $G$ of odd order $n \geq 5$, $|\rho_2| \cdot \omega \leq m-2$, with equality if and only if $G$ consists of two complete graphs of orders $\frac{n+1}{2}$ and $\frac{n-1}{2}$ joined by an edge or a path. For even $n \geq 2$, the quantity $|\rho_2| \cdot \omega - m$ is maximized exactly when $G$ is the join of two copies of $K_{n/2}$ by an edge.
The core of the methods developed in this paper is to regard a connected graph as an internally disconnected graph with Dirichlet boundary condition. This perspective allows us to transfer nodal domain techniques from continuous spectral geometry to discrete settings and to obtain sharp extremal characterizations across diverse graph classes.

Submission history

From: Zhe You [view email]
[v1] Wed, 10 Jun 2026 04:53:20 UTC (84 KB)
[v2] Mon, 15 Jun 2026 05:40:31 UTC (84 KB)