2022/02/13 by Yanni Zhai, Xiying Yuan, Zhai, Yanni +3
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2202.06249
openalex publication_date 2022/02/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Given a graph H and an integer p (p≥ 2), the edge blow-up Hp+1 of H is the graph obtained from replacing each edge in H by a clique of order (p+1), where the new vertices of the cliques are all distinct. The Turán numbers for edge blow-up of matchings were first studied by Erdős and Moon. Very recently some substantial progress of the extremal graphs for Hp+1 of larger p has been made by Yuan. The range of Turán numbers for edge blow-up of all bipartite graphs when p≥ 3 and the exact Turán numbers for edge blow-up of all non-bipartite graphs when p≥ χ(H) +1 has been determined by Yuan (2022), where χ(H) is the chromatic number of H. A lollipop Ck, ℓ is the graph obtained from a cycle Ck by appending a path Pℓ+1 to one of its vertices. In this paper, we consider the extremal graphs for Ck, ℓp+1 of the rest cases p=2 and p=3.