Extremal P_(8)-Free/P_(9)-Free Planar Graphs  

作　　者：Yong-Xin Lan Yong-Tang Shi 

机构地区：[1]School of Science,Hebei University of Technology,Tianjin,300401,China [2]Center for Combinatorics and LPMC,Nankai University,Tianjin,300071,China

出　　处：《Journal of the Operations Research Society of China》2023年第3期451-457,共7页中国运筹学会会刊（英文）

基　　金：the National Natural Science Foundation of China(Nos.11922112 and 11771221);the Natural Science Foundation of Tianjin(Nos.20JCZDJC00840 and 20JCJQJC00090);Yong-Xin Lan was partially supported by the National Natural Science Foundation of China(No.12001154);the Natural Science Foundation of Hebei Province(No.A2021202025);the Special Funds for Jointly Building Universities of Tianjin(No.280000307).

摘　　要：An H-free graph is a graph not containing the given graph H as a subgraph.It is well known that the Turán number ex(n,H)is the maximum number of edges in an H-free graph on n vertices.Based on this definition,we define ex_(P)(n,H)to restrict the graph classes to planar graphs,that is,ex_(P)(n,H)=max{|E(G)|:G∈G,where G is a family of all H-free planar graphs on n vertices.Obviously,we have ex_(P)(n,H)=3n−6 if the graph H is not a planar graph.The study is initiated by Dowden(J Graph Theory 83:213–230,2016),who obtained some results when H is considered as C_(4)or C_(5).In this paper,we determine the values of ex_(P)(n,Pk)with k∈{8,9},where Pk is a path with k vertices.

关 键 词：Turán number Extremal graph Planar graph 

分 类 号：O15[理学—数学]