A Non-aligning Variant of Generalized Turan Problems

被引:0
作者
Gerbner, Daniel [1 ]
机构
[1] Alfred Renyi Inst Math, Budapest, Hungary
关键词
INDUCIBILITY; COPIES; NUMBER;
D O I
10.1007/s00026-023-00640-8
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
In the so-called generalized Turan problems we study the largest number of copies of H in an n-vertex F-free graph G. Here we introduce a variant, where F is not forbidden, but we restrict how copies of H and F can be placed in G. More precisely, given an integer n and graphs H and F, what is the largest number of copies of H in an n-vertex graph such that the vertex set of that copy does not contain and is not contained in the vertex set of a copy of F? We solve this problem for some instances, give bounds in other instances, and we use our results to determine the generalized Turan number for some pairs of graphs.
引用
收藏
页码:351 / 366
页数:16
相关论文
共 27 条
[1]   Many T copies in H-free graphs [J].
Alon, Noga ;
Shikhelman, Clara .
JOURNAL OF COMBINATORIAL THEORY SERIES B, 2016, 121 :146-172
[2]  
BOLLOBAS B, 1976, MATH PROC CAMBRIDGE, V79, P19, DOI 10.1017/S0305004100052063
[3]  
Bondy J. A., 1974, Journal of Combinatorial Theory, Series B, V16, P97, DOI 10.1016/0095-8956(74)90052-5
[4]   THE INDUCIBILITY OF COMPLETE BIPARTITE GRAPHS [J].
BROWN, JI ;
SIDORENKO, A .
JOURNAL OF GRAPH THEORY, 1994, 18 (06) :629-645
[5]   Enumerating maximal independent sets with applications to graph colouring [J].
Byskov, JM .
OPERATIONS RESEARCH LETTERS, 2004, 32 (06) :547-556
[6]  
ErdHos P., 1959, Acta Math. Acad. Sci. Hungar., V10, P337, DOI [10.1007/BF02024498, DOI 10.1007/BF02024498]
[7]   COMPACTNESS RESULTS IN EXTREMAL GRAPH-THEORY [J].
ERDOS, P ;
SIMONOVITS, M .
COMBINATORICA, 1982, 2 (03) :275-288
[8]  
ERDOS P, 1984, PROGR GRAPH THEORY, P203
[9]   ON A CLASS OF DEGENERATE EXTREMAL GRAPH PROBLEMS [J].
FAUDREE, RJ ;
SIMONOVITS, M .
COMBINATORICA, 1983, 3 (01) :83-93
[10]   On 3-uniform hypergraphs without a cycle of a given length [J].
Furedi, Zoltan ;
Ozkahya, Lale .
DISCRETE APPLIED MATHEMATICS, 2017, 216 :582-588