2024/11/26 by Zejun Huang, Jiahui Liu, Huang, Zejun +3
Computer Science · Engineering · Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Matrix Theory and Algorithms #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.2411.17371
openalex publication_date 2024/11/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let G be a connected nonregular graphs of order n with maximum degree Δ that attains the maximum spectral radius. Liu and Li (2008) proposed a conjecture stating that G has a degree sequence (Δ,…,Δ,δ) with δ<Δ. For Δ=3 and Δ=4, Liu (2024) confirmed this conjecture by characterizing the structure of such graphs. Liu also proposed a modified version of the conjecture for fixed Δ and sufficiently large n, stating that the above δ=Δ-1 if Δ and n are both odd, δ=1 if Δ is odd and n is even, and δ=Δ-2 if Δ is even. For the cases where Δ=n-2 with n≥ 5, and Δ=n-3 with n≥ 59, we fully characterize the structure of G.