Existence of trees with prescribed maximum degrees and spectral radii
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918139607908352 |
|---|---|
| author | Dong, Fengming Zhang, Ruixue |
| author_facet | Dong, Fengming Zhang, Ruixue |
| contents | It is well known that the spectral radius $ρ(T)$ of a tree $T$ with at least $3$ vertices has the property that $\frac 14ρ(T)^2+1<Δ(T)\le ρ(T)^2$, where $Δ(T)$ is the maximum degree of $T$. Let $\mathbb{P}$ denote the set of spectral radii of all non-trivial trees. In this article, we study the inverse problem that for any $α\in \mathbb{P}$ and integer $r$ satisfying the condition $\frac 14α^2+1<r\le α^2$, is there a tree $T$ such that $Δ(T)=r$ and $ρ(T)=α$?
For any positive integer $r$ and positive number $α$, let ${\mathscr W}_r(α)$ denote a set of non-negative real numbers defined as follows: $α\in {\mathscr W}_r(α)$, and for any multi-set $\{q_i\in {\mathscr W}_r(α): q_i>0, 1\le i\le s\}$, if $β:=α-\sum\limits_{i=1}^sq_i^{-1}\ge 0$ and $s\le r-\left \lceil \fracβ{β+1}\right\rceil$, then $β\in {\mathscr W}_r(α)$. We first show that $0\in {\mathscr W}_r(α)$ if and only if there exists a tree $T$ with $Δ(T)\le r$ and $ρ(T)=α$. It follows directly that $\mathbb{P}$ is exactly the set of positive numbers $α$ such that $0\in {\mathscr W}_{\lfloorα^2\rfloor}(α)$. Applying this conclusion, we prove that for any two positive integers $r\ge 2$ and $k$, there exists a tree $T$ with $Δ(T)=r$ and $ρ(T)=\sqrt k$ if and only if $\frac 14 k+1<r\le k$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_06617 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Existence of trees with prescribed maximum degrees and spectral radii Dong, Fengming Zhang, Ruixue Combinatorics 05C05, 05C20, 05C50 It is well known that the spectral radius $ρ(T)$ of a tree $T$ with at least $3$ vertices has the property that $\frac 14ρ(T)^2+1<Δ(T)\le ρ(T)^2$, where $Δ(T)$ is the maximum degree of $T$. Let $\mathbb{P}$ denote the set of spectral radii of all non-trivial trees. In this article, we study the inverse problem that for any $α\in \mathbb{P}$ and integer $r$ satisfying the condition $\frac 14α^2+1<r\le α^2$, is there a tree $T$ such that $Δ(T)=r$ and $ρ(T)=α$? For any positive integer $r$ and positive number $α$, let ${\mathscr W}_r(α)$ denote a set of non-negative real numbers defined as follows: $α\in {\mathscr W}_r(α)$, and for any multi-set $\{q_i\in {\mathscr W}_r(α): q_i>0, 1\le i\le s\}$, if $β:=α-\sum\limits_{i=1}^sq_i^{-1}\ge 0$ and $s\le r-\left \lceil \fracβ{β+1}\right\rceil$, then $β\in {\mathscr W}_r(α)$. We first show that $0\in {\mathscr W}_r(α)$ if and only if there exists a tree $T$ with $Δ(T)\le r$ and $ρ(T)=α$. It follows directly that $\mathbb{P}$ is exactly the set of positive numbers $α$ such that $0\in {\mathscr W}_{\lfloorα^2\rfloor}(α)$. Applying this conclusion, we prove that for any two positive integers $r\ge 2$ and $k$, there exists a tree $T$ with $Δ(T)=r$ and $ρ(T)=\sqrt k$ if and only if $\frac 14 k+1<r\le k$. |
| title | Existence of trees with prescribed maximum degrees and spectral radii |
| topic | Combinatorics 05C05, 05C20, 05C50 |
| url | https://arxiv.org/abs/2504.06617 |