河北师范大学学报—

期刊信息

刊名：河北师范大学学报（自然科学版）Journal of Hebei Normal University (Natural Science)
主办：河北师范大学
ISSN： 1000-5854
CN： 13-1061/N
中国科技核心期刊
中国期刊方阵入选期刊
中国高校优秀科技期刊
华北优秀期刊
河北省优秀科技期刊

协同采编系统

友情链接

P₅∪P₉的Turán数

(天津大学数学学院，天津 300350)
DOI： 10.13763/j.cnki.jhebnu.nse.202101003

The Turán Number of P₅∪P₉

TIAN Hong,HU Yumei

PDF
下载
HTML

摘要/Abstract

摘要：

极值图论是组合数学的一个分支，主要研究对于给定的一类图，确定其中某些参数的极值，所讨论的Turán数属于图论中的极值问题. 图H的Turán数是指不包含H作为子图的n阶图的最大边数，记作e_x（n，H）. 确定了e_x（n，P₅∪P₉）=max{[n，14，5]，5n-14}，其中[n，14，5]=117+3n+r（r-4）/2，n-13≡r（mod 4），对应的极值图为K₁₃∪H和K₅+（K₂∪K_n-7），这里H∈E_X（n-13，P₅）.

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 e_x(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 e_x(n,P₅∪P₉)=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 K₁₃∪H for H∈E_X(n-13,P₅) and K₅+(K₂∪K_n-7).

关键词

关键词： Turán数 ; 极值图 ; 不交路 ; P₅∪P₉

Key words： Turan number ; extremal graphs ; disjoint paths ; P₅∪P₉

参考文献 10

[1] LAN Y,QIN Z,SHI Y.The Turán Number of 2P₇[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,LIDICKYB,PALMER C.On the Turan 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

P₅∪P₉的Turán数

The Turán Number of P5∪P9

摘要/Abstract

关键词

参考文献 10

The Turán Number of P₅∪P₉