在线阅读 --自然科学版 2021年1期《P5P9的Turán数》
P5P9的Turán数--[在线阅读]
田宏, 胡玉梅
天津大学 数学学院, 天津 300350
起止页码: 15--18页
DOI: 10.13763/j.cnki.jhebnu.nse.202101003
摘要
极值图论是组合数学的一个分支,主要研究对于给定的一类图,确定其中某些参数的极值,所讨论的Turán数属于图论中的极值问题.图H的Turán数是指不包含H作为子图的n阶图的最大边数,记作exn,H).确定了exnP5P9)=max{[n,14,5],5n-14},其中[n,14,5]=117+3n+rr-4)/2,n-13≡r(mod 4),对应的极值图为K13HK5+(K2Kn-7),这里HEXn-13,P5).

The Turán Number of P5P9
TIAN Hong, HU Yumei
College of Mathematics, Tianjin University, Tianjin 300350, China
Abstract:
Extremal graph theory is a branch of combinatorics mathematics.It mainly studies the extremal values of some parameters for a given family of graph.The Turán number mainly discussed in this paper belongs to the extremal problem in graph theory.The Turán number of a graph H,denoted by ex(n,H),is the maximum number of edges in any graph of order n which does not contain H as a subgraph.In this paper,we determine ex(n,P5P9)=max{[n,14,5],5n-14},where [n,14,5]=117+3n+r(r-4)/2,n-13≡r(mod 4),moreover, the extremal graphs are K13H for HEX(n-13,P5) and K5+(K2Kn-7).

收稿日期: 2019-10-25
基金项目:

参考文献:
[1]LAN Y,QIN Z,SHI Y.The Turán Number of 2P7[J].Discuss Math Graph Theory,2019,39(4):805-814.doi:10.7151/dmgt.2111
[2]FAUDREE R J,SCHELP R H.Path Ramsey Numbers in Multicolorings[J].J Combin Theory Ser B,1975,19(2):150-160.doi:10.1016/0095-8956(75)90080-5
[3]BALISTER P N,GYÖRI E,LEHEL J,et al.Connected Graphs Without Long Paths[J].Distrete Math,2008,308(19):4487-4494.doi:10.1016/j.disc.2007.08.047
[4]KOPYLOV G N.Maximal Paths and Cycles in a Graph[J].Dokl Akad Nauk SSSR,1977,18(1):19-21.doi:10.1016/0361-3658(77)90019-4
[5]TURÁN P.On the Theory of Graphs[J].Colloq Math,1954,3(1):19-30.doi:10.4064/cm-3-1-19-30
[6]ERDÖS P.Über Ein Extremalproblem in Der Graphentheorie[J].Arch Math,1962,13(1):222-227.doi:10.1007/bf01650069
[7]MOON J W.On Independent Complete Subgraphs in a Graph[J].Canad J Math,1968,20(1):95-102.doi:10.4153/cjm-1968-012-x
[8]BUSHAW N,KETTLE N.Turán Numbers of Multiple Paths and Equibipartite Forests[J].Combin Probab Comput,2011,20(6):837-853.doi:10.1017/s0963548311000460
[9]LIU H,LIDICKÝ B,PALMER C.On the Turàn Number of Forests[J].Macromolecules,2013,42(6):2088-2092.doi:10.37236/3142
[10]YUAN L T,ZHANG X D.The Turán Number of Disjoint Copies of Paths[J].Discrete Math,2015,340(2):132-139.doi:10.1016/j.disc.2016.08.004