The First Eigenvalue of the Discrete Dirichlet Problem for a Graph

We give a graph theoretic analogue of the celebrated Faber-Krahn inequality, that is, the first eigenvalue \(\lambda_1(\Omega)\) of the Dirichlet problem for a bounded domain \(\Omega\) in the Euclidean space \(\mathbf{R}^n\) satisfies, \(\lambda_1(\Omega) \geq \lambda_1(\mathbf{B})\) if \(\text{vol}(\Omega) = \text{vol}(\mathbf{B})\), and equality holds only when \(\Omega\) is a ball \(\mathbf{B}\).

The first eigenvalue \(\lambda_1(G)\) of the Dirichlet problem of a graph \(G = (V, E)\) with boundary satisfies, if the number of edges equals \(m\), \(\lambda_1(G) \geq \lambda_1(L_m)\), and equality holds only when \(G\) is the linear graph \(L_m\).