The First Eigenvalue of the Discrete Dirichlet Problem for a Graph

Abstract

We give a graph theoretic analogue of the celebrated Faber-Krahn inequality, that is, the first eigenvalue ${\lambda }_1(\mathrm{\Omega })$ of the Dirichlet problem for a bounded domain $\mathrm{\Omega }$ in the Euclidean space ${\mathbf{R}}^n$ satisfies, ${\lambda }_1(\mathrm{\Omega })\ge {\lambda }_1(\mathbf{B})$ if $\text{vol}(\mathrm{\Omega })=\text{vol}(\mathbf{B})$, and equality holds only when $\mathrm{\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)\ge {\lambda }_1(L_m)$, and equality holds only when $G$ is the linear graph $L_m$.