2023/10/08 by Longfei Fang, Huiqiu Lin, Fang, Longfei +1 · 2 citations
Materials Science · Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Magnetism in coordination complexes
paper · pdf · doi:10.48550/arxiv.2310.05085
openalex publication_date 2023/10/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let \rm ex(n,F) and \rm spex(n,F) be the maximum size and maximum spectral radius of an F-free graph of order n, respectively. The value \rm spex(n,F) is called the spectral extremal value of F. Nikiforov [J. Graph Theory 62 (2009) 362--368] gave the spectral Stability Lemma, which implies that for every ε>0, sufficiently large n and a non-bipartite graph H with chromatic number χ(H), the extremal graph for \rm spex(n,H) can be obtained from the Turán graph Tχ(H)-1(n) by adding and deleting at most ε n2 edges. It is still a challenging problem to determine the exact spectral extremal values of many non-bipartite graphs. Given a graph F and an integer p≥ 2, the edge blow-up of F, denoted by Fp+1, is the graph obtained from replacing each edge in F by a Kp+1 where the new vertices of Kp+1 are all distinct. In this paper, we determine the exact spectral extremal values of the edge blow-up of all non-bipartite graphs and provide the asymptotic spectral extremal values of the edge blow-up of all bipartite graphs for sufficiently large n, which can be seen as a spectral version of the theorem on \rm ex(n,Fp+1) given by Yuan [J. Combin. Theory Ser. B 152 (2022) 379--398]. As applications, on the one hand, we generalize several previous results on \rm spex(n,Fp+1) for F being a matching and a star for p≥ 3. On the other hand, we obtain the exact values of \rm spex(n,Fp+1) for F being a path, a cycle and a complete graph.