论文标题
规定最大程度的非规范图的极端光谱半径
Extremal spectral radius of nonregular graphs with prescribed maximum degree
论文作者
论文摘要
令$ g $为图形，在所有连接的非规范图$ n $的最大频谱半径（最大程度$δ$）中达到最大光谱半径。令$λ_1（g）$为$ g $的频谱半径。由于刘，沉和王而引起的一个很好的猜想[在最大的非规范图的特征值上，J。Bombin。理论ser。 B，97（2007）1010--1018]断言，对于每个固定$δ$关于极端图的重要结构特性$ g $，刘和李提出了另一个猜想，该猜想指出$ g $具有级序列$δ，\ ldots，δ，δ$。在这里，$δ=δ-1 $或$δ=δ-2$，具体取决于$nδ$的均衡。在本文中，我们在两个猜想上取得了进展。确切地说，我们通过表明上限最多为$π^2/2 $来反驳所有$δ\ geq 3 $的第一个猜想。对于小$δ$，我们确定$δ-λ_1（g）$的精确渐近行为。特别是，我们表明$ \ lim \ limits_ {n \ to \ infty} n^2（δ-λ_1（g）） /（δ-1）=π^2 /4 $如果$δ= 3 $;和$ \ lim \ limits_ {n \ to \ infty} n^2（δ-λ_1（g）） /（δ-2）=π^2 /2 $如果$δ= 4 $。我们还通过确定极端图的精确结构来确认$δ= 3 $和$δ= 4 $的第二个猜想。特别是，我们表明$δ\ in \ {3,4 \} $的极端图必须具有从特定块中构建的类似路径的结构。
Let $G$ be a graph attaining the maximum spectral radius among all connected nonregular graphs of order $n$ with maximum degree $Δ$. Let $λ_1(G)$ be the spectral radius of $G$. A nice conjecture due to Liu, Shen and Wang [On the largest eigenvalue of non-regular graphs, J. Combin. Theory Ser. B, 97 (2007) 1010--1018] asserts that \[ \lim_{n\to\infty} \frac{n^2(Δ-λ_1(G))}{Δ-1} = π^2 \] for each fixed $Δ$. Concerning an important structural property of the extremal graphs $G$, Liu and Li present another conjecture which states that $G$ has degree sequence $Δ,\ldots,Δ,δ$. Here, $δ=Δ-1$ or $δ=Δ-2$ depending on the parity of $nΔ$. In this paper, we make progress on the two conjectures. To be precise, we disprove the first conjecture for all $Δ\geq 3$ by showing that the limit superior is at most $π^2/2$. For small $Δ$, we determine the precise asymptotic behavior of $Δ-λ_1(G)$. In particular, we show that $\lim\limits_{n\to\infty} n^2 (Δ- λ_1(G)) /(Δ- 1) = π^2/4$ if $Δ=3$; and $\lim\limits_{n\to\infty} n^2 (Δ- λ_1(G)) /(Δ- 2) = π^2/2$ if $Δ= 4$. We also confirm the second conjecture for $Δ= 3$ and $Δ= 4$ by determining the precise structure of extremal graphs. Particularly, we show that the extremal graphs for $Δ\in\{3,4\}$ must have a path-like structure built from specific blocks.
