Abstract | ||
---|---|---|
Fix graphs F and H and let ex(n,H,F) denote the maximum possible number of copies of the graph H in an n-vertex F-free graph. The systematic study of this function was initiated by Alon and Shikhelman [J. Comb. Theory, B. 121 (2016)]. In this paper, we give new general bounds concerning this generalized Turán function. We also determine ex(n,Pk,K2,t) (where Pk is a path on k vertices) and ex(n,Ck,K2,t) asymptotically for every k and t. For example, it is shown that for t≥2 and k≥5 we have ex(n,Ck,K2,t)=12k+o(1)(t−1)k∕2nk∕2. We also characterize the graphs F that cause the function ex(n,Ck,F) to be linear in n. In the final section we discuss a connection between the function ex(n,H,F) and Berge hypergraph problems. |
Year | DOI | Venue |
---|---|---|
2019 | 10.1016/j.ejc.2019.103001 | European Journal of Combinatorics |
Field | DocType | Volume |
Discrete mathematics,Graph,Combinatorics,Vertex (geometry),Hypergraph,Mathematics | Journal | 82 |
ISSN | Citations | PageRank |
0195-6698 | 1 | 0.36 |
References | Authors | |
11 | 2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Dániel Gerbner | 1 | 46 | 21.61 |
Cory Palmer | 2 | 44 | 10.33 |