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}\setminus \{1\}$ 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 a positive integer $r$ and a positive real number $\alpha$, let ${\mathcal{W}}_r(\alpha )$ be the smallest subset of $[0,\infty )$ containing $\alpha$ and closed under the following operation: if $q_1,\dots ,q_s$ are positive elements of ${\mathcal{W}}_r(\alpha )$, not necessarily distinct, and $q=\alpha -{\sum }_{i=1}^s{q}_i^{-1}$, then $q\in {\mathcal{W}}_r(\alpha )$ whenever either $1\le s<r$ and $q\ge 0$, or $s=r$ and $q=0$. 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$. Moreover, there exists a tree $T$ with $\Delta (T)=r$ and $\rho (T)=\alpha$ if and only if there are positive elements $q_1,\dots ,q_r\in {\mathcal{W}}_r(\alpha )$, not necessarily distinct, satisfying ${\sum }_{i=1}^r{q}_i^{-1}=\alpha$. Consequently, $\mathbb{P}=\{\alpha \ge 1: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$.

arXiv comment20 pages and 1 figures