Spectral Radius of Graphs with Size Constraints: Resolving a Conjecture of Guiduli

Abstract

We resolve a problem posed by Guiduli (1996) on the spectral radius of graphs satisfying the Hereditarily Bounded Property $P_{t,r}$, which requires that every subgraph $H$ with $|V(H)|\ge t$ satisfies $|E(H)|\le t|V(H)|+r$. For an $n$-vertex graph $G$ satisfying $P_{t,r}$, where $t>0$ and $r\ge -\left(\genfrac{}{}{0ex}{}{\lfloor t+1\rfloor }{2}\right)$, we prove that the spectral radius $\ddot{I}(G)$ is bounded above by $\ddot{I}(G)\le c(s,t)+\sqrt{\lfloor t\rfloor n}$, where $s=\left(\genfrac{}{}{0ex}{}{\lfloor t\rfloor +1}{2}\right)+r$, thus affirmatively answering Guiduli's conjecture. Furthermore, we present a complete characterization of the extremal graphs that achieve this bound. These graphs are constructed as the join graph $K_{\lfloor t\rfloor }\nabla F$, where $F$ is either $K_3\cup (n-\lfloor t\rfloor -3)K_1$ or a forest consisting solely of star structures. The specific structure of such forests is meticulously characterized. Central to our analysis is the introduction of a novel potential function $\hat{I}\cdot (F)=e(F)+(\lfloor t\rfloor -t)|V(F)|$, which quantifies the structural "positivity" of subgraphs. By combining edge-shifting operations with spectral radius maximization principles, we establish sharp bounds on $\hat{I}{\cdot }^{+}(G)$, the cumulative positivity of $G$. Our results contribute to the understanding of spectral extremal problems under edge-density constraints and provide a framework for analyzing similar hereditary properties.