Please wait a minute...
北京大学期刊网 | 作者  审稿人  编委专家  工作人员

首页   |   关于   |   浏览   |   投稿指南   |   新闻公告
数学进展 - 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
    /   /   推荐

摘要 令$G$表示$n$个顶点的图. 图$G$的一个线性森林是$G$中由顶点不交的路以及孤立点组成的子图. 其中, $G$的边数最多的线性森林称为图$G$的最大线性森林, 用$l(G)$表示最大线性森林的边数. 设定$t=\big\lfloor \frac{k-1}2\big \rfloor$. 令$r_3(G)$表示图$G$中三角形的个数. 在本文中, 我们证明了如果$l(G)=k-1$且$\delta(G)\geq \delta$, 那么对于任意的$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\}$.
其中, 当$k$为奇数时, $d=0$, 否则$d=t$.
关键词 广义Turán数线性森林三角形$k$-闭包    
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  
基金资助:国家自然科学基金 (No. 11701407).
通讯作者: E-mail: * wangjian01@tyut.edu.cn   
[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   
首页 · 关于 · 关于OA · 法律公告 · 收录须知 · 联系我们 · 注册 · 登录


© 2015-2017 北京大学图书馆 .