北京大学期刊网　|　作者　　审稿人　　编委专家　　工作人员 首页　  |  　关于　  |  　浏览　  |  　投稿指南　  |  　新闻公告
 数学进展 - 2020, Vol. 49(4): 406-412
 研究论文
 关于线性森林的广义图兰问题研究 The Generalized Turán Number of Linear Forests 段秀转, 王健*, 杨卫华 DUAN Xiuzhuan, WANG Jian, YANG Weihua 太原理工大学数学学院, 太原, 山西, 030024 College of Mathematics, Taiyuan University of Technology, Taiyuan, Shanxi, 030024, P. R. China 收稿日期: 2019-05-14 出版日期: 2020-08-11 2020, Vol. 49(4): 406-412 DOI: 10.11845/sxjz.2019052b
 PDF [310 KB] 91 下载 151 浏览 引用导出
0
/   /   推荐

$r_3(G)\leq max \Bigg\{\Bigg(\mathop{}_{3}^{k-\delta} \Bigg)+\Bigg( \mathop{}_{2}^{\delta}\Bigg)(n-k+\delta),\Bigg( \mathop{}_{3}^{t}\Bigg)+\Bigg( \mathop{}_{2}^{t}\Bigg)(n-t)+d \Bigg\}$.

Abstract：Let $G$ be a graph on $n$ vertices. A linear forest is a graph consisting of vertex-disjoint paths and isolated vertices. A maximum linear forest of $G$ is a subgraph of $G$ with maximum number of edges, which is a linear forest. We denote by $l(G)$ this maximum number. Let $t=\big\lfloor \frac{k-1}2\big\rfloor$. Let $r_3(G)$ be the number of triangles in $G$. We prove that if $l(G)=k-1$ and $\delta(G)= \delta$, then for any $k＜n$,
$r_3(G)\leq max \Bigg\{\Bigg(\mathop{}_{3}^{k-\delta} \Bigg)+\Bigg( \mathop{}_{2}^{\delta}\Bigg)(n-k+\delta),\Bigg( \mathop{}_{3}^{t}\Bigg)+\Bigg( \mathop{}_{2}^{t}\Bigg)(n-t)+d \Bigg\}$.
where $d=0$ if $k$ is odd and $d=t$ otherwise.
Key wordsgeneralized Turán number    linear forests    triangles    $k$-closure
 PACS: O157.5

 [1] Alon, N. and Shikhelman, C., Many $T$-copies in $H$-free graphs, J. Combin. Theory Ser. B, 2016, 121: 146-172.[2] Bollobás, B. and Györi, E., Pentagons vs. triangles, Discrete Math., 2008, 308: 4332-4336.[3] Bondy, J.A. and Chvatal, V., A method in graph theory, Discrete Math., 1976, 15: 111-135.[4] Erdös P.,On the number of complete subgraphs contained in certain graphs, Publ. Math. Inst. Hung. Acad. Sci., 1962, 7: 459-464.[5] Erdös, P. and Gallai, T., On maximal paths and circuits of graphs, Acta Math. Acad. Sci. Hungar., 1959, 10: 337-356.[6] Ergemlidze B., Methuku A., Salia N. and Györi E., A note on the maximum number of triangles in a $C_{5}$-free graph, J. Graph Theory, 2019, 90(3): 227-230.[7] Füredi Z., Kostochka A. and Luo R., Extensions of a theorem of Erdös on nonhamiltonian graphs, J. Graph Theory, 2018, 89(2): 176-193.[8] Füredi, Z. and Özkahya, L., On 3-uniform hypergraphs without a cycle of a given length, Discrete Applied Math., 2017, 216: 582-588.[9] Gerbner D., Methuku A. and Vizer M., Generalized Turán problems for disjoint copies of graphs, Discrete Math., 2019, 11: 3130-3141.[10] Gerbner, D. and Palmer, C., Counting copies of a fixed subgraph in $F$-free graphs, European J. Combin., 2019, 82: 103001, 15 pp.[11] Györi, E. and Li, H., The maximum number of triangles in $C_{2k+1}$-free graph, J. Combin. Theory Ser. B, 2012, 102: 1061-1066.[12] Keevash P.,Hypergraph Turán problems, Surveys in Combinatorics, 2011, 392: 83-140.[13] Li, B.L. and Ning, B., Spectral analogues of Erdös' and Moon-Moser's theorems on Hamilton cycles, Linear Multilinear Algebra, 2016, 64: 2252-2269.[14] Luo R.,The maximum number of cliques in graphs without long cycles, J. Combin. Theory Ser. B, 2017, 128: 219-226.[15] Ning, B. and Wang, J., The formula for Turán number of spanning linear forests, Discrete Math., 2020, 343(8): 111924, 6 pp.[16] Ma, J. and Qiu, Y., Some sharp results on the generalized Turán numbers, European J. Combin., 2020, 84: 103026, 16 pp.[17] Sidorenko A.,What we know and what we do not know about Turán numbers, Graphs Combinatorics, 1995, 11: 179-199.[18] Simonovits M.,Paul Erdös' influence on extremal graph theory, The mathematics of Paul Erdös, II, Algorithms Combin., 1997, 14: 148-192.[19] Wang, J. and Yang, W.H., The Turán number for spanning linear forests, Discrete Appl. Math., 2019, 254: 291-294.
 [1] 陈洪京, 苏战军, 张小朋. 凸多边形的全等等腰直角三角形铺砌[J]. 数学进展, 2019, 48(5): 592-606. [2] 景昱波,王应前. 可平面图的线性2-荫度的新上限[J]. 数学进展, 2016, 45(2): 185-189. [3] 王晓. 不含三角形的某些禁用子图的色数[J]. 数学进展, 2015, 44(5): 747-751.
Viewed
Full text

Abstract

Cited

Discussed