关于线性森林的广义图兰问题研究  

The Generalized Turán Number of Linear Forests

作　　者：段秀转 王健 杨卫华 DUAN Xiuzhuan;WANG Jian;YANG Weihua(College of Mathematics,Taiyuan University of Technology,Taiyuan,Shanxi,030024,P.R.China)

机构地区：[1]太原理工大学数学学院,太原山西030024

出　　处：《数学进展》2020年第4期406-412,共7页Advances in Mathematics（China）

基　　金：国家自然科学基金(No.11701407)。

摘　　要：令G表示n个顶点的图.图G的一个线性森林是G中由顶点不交的路以及孤立点组成的子图.其中,G的边数最多的线性森林称为图G的最大线性森林,用l(G)表示最大线性森林的边数.设定t=[k-1/2].令r3(G)表示图G中三角形的个数.在本文中,我们证明了如果l(G)=k-1且δ(G)≥δ,那么对于任意的k<n,r3(G)≤max{(k-δ/3)+(δ/2)(n-k+δ),(t/3)+(t/2)(n-t)+d}其中,当k为奇数时,d=0,否则d=t.Let G be a graph on n vertices.A linear forest is a graph consisting of vertexdisjoint 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.Lett=[k-1/2].Let r3(G)be the number of triangles in G.We prove that if l(G)=k-1 andδ(G)=δ,then for any k<n,r3(G)≤max{(k-δ/3)+(δ/2)(n-k+δ),(t/3)+(t/2)(n-t)+d} where d=0 if k is odd and d=t otherwise.

关 键 词：广义Turán数 线性森林 三角形 k-闭包 

分 类 号：O157.5[理学—数学]