2024/12/09 by Rui Li, Li, Rui, Anyao Wang +2
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Graph theory and applications
paper · pdf · doi:10.48550/arxiv.2412.06375
openalex publication_date 2024/12/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We resolve a problem posed by Guiduli (1996) on the spectral radius of graphs satisfying the Hereditarily Bounded Property Pt,r, which requires that every subgraph H with |V(H)| ≥ t satisfies |E(H)| ≤ t|V(H)| + r. For an n-vertex graph G satisfying Pt,r, where t > 0 and r ≥ -\binom\lfloor t+1 \rfloor2, we prove that the spectral radius ρ(G) is bounded above by ρ(G) ≤ c(s,t) + √(\lfloor t \rfloor n), where s = \binom\lfloor t \rfloor + 12 + 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 ∇ F, where F is either K3 ∪ (n - \lfloor t \rfloor - 3)K1 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 η(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 η+(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.