2024/01/11 by Longfei Fang, Fang, Longfei, Huiqiu Lin +5 · 2 citations
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications
paper · pdf · doi:10.48550/arxiv.2401.05786
openalex publication_date 2024/01/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let \rm spex(n,F) be the maximum spectral radius over all F-free graphs of order n, and \rm SPEX(n,F) be the family of F-free graphs of order n with spectral radius equal to \rm spex(n,F). Given integers n,k,p with n>k>0 and 0≤ p≤ \lfloor(n-k)/2\rfloor, let Sn,kp be the graph obtained from Kk∇(n-k)K1 by embedding p independent edges within its independent set, where `∇' means the join product. For n≥ℓ≥ 4, let Gn,ℓ=Sn,(ℓ-2)/20 if ℓ is even, and Gn,ℓ=Sn,(ℓ-3)/21 if ℓ is odd. Cioabă, Desai and Tait [SIAM J. Discrete Math. 37 (3) (2023) 2228--2239] showed that for ℓ≥ 6 and sufficiently large n, if ρ(G)≥ ρ(Gn,ℓ), then G contains all trees of order ℓ unless G=Gn,ℓ. They further posed a problem to study \rm spex(n,F) for various specific trees F. Fix a tree F of order ℓ≥ 6, let A and B be two partite sets of F with |A|≤ |B|, and set q=|A|-1. We first show that any graph in \rm SPEX(n,F) contains a spanning subgraph Kq,n-q for q≥ 1 and sufficiently large n. Consequently, ρ(Kq,n-q)≤ \rm spex(n,F)≤ ρ(Gn,ℓ), we further respectively characterize all trees F with these two equalities holding. Secondly, we characterize the spectral extremal graphs for some specific trees and provide asymptotic spectral extremal values of the remaining trees. In particular, we characterize the spectral extremal graphs for all spiders, surprisingly, the extremal graphs are not always the spanning subgraph of Gn,ℓ.