Extremal graphs for blow-ups of stars and paths
2020
Abstract The blow-up of a graph F is the graph obtained from F by replacing each edge in F by a clique of the same size where the new vertices of the cliques are all different. Given a forbidden graph H and a positive integer n , the extremal number, ex ( n , H ) , is the maximum number of edges in a graph on n vertices that does not contain H as a subgraph. When forbidding multiple graphs, ex ( n , H 1 , H 2 , … , H k ) denotes the maximum number of edges in an n -vertex graph with no subgraph H i for 1 ≤ i ≤ k . Erdos et al. and Chen et al. determined the extremal number of blow-ups of stars. Liu and Glebov determined the extremal numbers of the blow-ups of paths, cycles and a large class of trees respectively. In this paper we determine the extremal number and find the extremal graphs for both blow-up of stars and blow-up of paths, when n is sufficiently large.
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
7
References
0
Citations
NaN
KQI