Faber-Krahn type inequality for supertrees

Abstract

The Faber-Krahn inequality states that the first Dirichlet eigenvalue among all bounded domains is no less than a Euclidean ball with the same volume in ${\mathbb{R}}^n$ \cite{Chavel FB}. Bıyıkoğlu and Leydold (J. Comb. Theory, Ser. B., 2007) demonstrated that the Faber-Krahn inequality also holds for the class of trees with boundary with the same degree sequence and characterized the unique extremal tree. Bıyıkoğlu and Leydold (2007) also posed a question as follows: Give a characterization of all graphs in a given class $\mathcal{C}$ with the Faber-Krahn property. In this paper, we address this question specifically for $k$-uniform supertrees with boundary. We introduce a spiral-like ordering (SLO-ordering) of vertices for supertrees, an extension of the SLO-ordering for trees initially proposed by Pruss [ Duke Math. J., 1998], and prove that the SLO-supertree has the Faber-Krahn property among all supertrees with a given degree sequence. Furthermore, among degree sequences that have a minimum degree $d$ for interior vertices, the SLO-supertree with degree sequence $(d,\dots ,d,d^{\prime },1,\dots ,1)$ possesses the Faber-Krahn property.

18 pages, 1 figure