Given a graph Hand an integer p, the edge blow-up Hp+1 of His 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 Turan numbers for edge blow-up of matchings were first studied by Erdos and Moon. In this paper, we determine the range of the Turan numbers for edge blow-up of all bipartite graphs and the exact Turan numbers for edge blow-up of all non-bipartite graphs. In addition, we characterize the extremal graphs for edge blow-up of all non-bipartite graphs. Our results also extend several known results, including the Turan numbers for edge blow-up of stars, paths and cycles. The method we used can also be applied to find a family of counter-examples to a conjecture posed by Keevash and Sudakov in 2004 concerning the maximum number of edges not contained in any monochromatic copy of H in a 2-edge-coloring of K-n. (C) 2021 Elsevier Inc. All rights reserved.
NSTL
Elsevier
