Trees with Prescribed Maximum Degree and Spectral Radius

Abstract

It is well known that the spectral radius $\rho (T)$ of a tree $T$ with at least $3$ vertices satisfies $\frac{1}{4}\rho (T{)}^2+1<\Delta (T)\le \rho (T{)}^2$, where $\Delta (T)$ is the maximum degree of $T$. Let $\mathbb{P}$ denote the set of spectral radii of all non-trivial trees. We ask whether, for every $\alpha \in \mathbb{P}$ and every integer $r$ satisfying $\frac{1}{4}{\alpha }^2+1<r\le {\alpha }^2$, there exists a tree $T$ such that $\Delta (T)=r$ and $\rho (T)=\alpha$. For any positive integer $r$ and positive real number $\alpha$, define ${\mathcal{W}}_r(\alpha )$ recursively as follows. Initially, $\alpha \in {\mathcal{W}}_r(\alpha )$. Next, for any multiset $\left\{q_i:1\le i\le s\right\}$ of positive elements of ${\mathcal{W}}_r(\alpha )$ with $q:=\alpha -\sum _{i=1}^s{q}_i^{-1}\ge 0$, if either $s<r$ and $q\ge 0$, or $s=r$ and $q=0$, then $q\in {\mathcal{W}}_r(\alpha )$. We prove that $0\in {\mathcal{W}}_r(\alpha )$ if and only if there exists a tree $T$ with $\Delta (T)\le r$ and $\rho (T)=\alpha$. Consequently, $\mathbb{P}$ is exactly the set of positive numbers $\alpha$ such that $0\in {\mathcal{W}}_{\lfloor {\alpha }^2\rfloor }(\alpha )$. As an application, we show that for integers $k,r\ge 2$, there exists a tree $T$ with $\Delta (T)=r$ and $\rho (T)=\sqrt{k}$ if and only if $\frac{1}{4}k+1<r\le k$.

19 pages and 1 figures