2022/07/07 by Xiaona Fang, Lihua You, Fang, Xiaona +1 · 2 citations
Computer Science · Mathematics · #05C35 #05C50 #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Graph theory and applications #Matrix Theory and Algorithms
paper · pdf · doi:10.48550/arxiv.2207.03045
openalex publication_date 2022/07/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let G be a graph of size m and ρ(G) be the spectral radius of its adjacency matrix. A graph is said to be F-free if it does not contain a subgraph isomorphic to F. In this paper, we prove that if G is a K2,r+1-free non-star graph with m≥ (4r+2)2+1, then ρ(G)≤ ρ(Sm1), with equality if and only if G≅ Sm1. Recently, Li, Sun and Wei showed that for any θ1,2,3-free graph of size m≥ 8, ρ(G)≤ (1+√(4m-3))/(2), with equality if and only if G≅ S(m+3)/(2),2. However, this bound is not attainable when m is even. We proved that if G is θ1,2,3-free and G\ncong S(m+3)/(2),2 with m≥ 22, then ρ(G)≤ ρ(Fm,1) if m is even, with equality if and only if G≅ Fm,1, and ρ(G)≤ ρ(Fm,2) if m is odd, with equality if and only if G≅ Fm,2.