Journal of the Operations Research Society of China ›› 2023, Vol. 11 ›› Issue (3): 451-457.doi: 10.1007/s40305-021-00385-2

• • 上一篇    下一篇

  

  • 收稿日期:2020-02-24 修回日期:2021-11-25 出版日期:2023-09-30 发布日期:2023-09-07
  • 通讯作者: Yong-Tang Shi, Yong-Xin Lan E-mail:shi@nankai.edu.cn;yxlan0@126.com

Extremal P8-Free/P9-Free Planar Graphs

Yong-Xin Lan1, Yong-Tang Shi2   

  1. 1. School of Science, Hebei University of Technology, Tianjin, 300401, China;
    2. Center for Combinatorics and LPMC, Nankai University, Tianjin, 300071, China
  • Received:2020-02-24 Revised:2021-11-25 Online:2023-09-30 Published:2023-09-07
  • Contact: Yong-Tang Shi, Yong-Xin Lan E-mail:shi@nankai.edu.cn;yxlan0@126.com
  • Supported by:
    Yong-Tang Shi was partially supported by 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) and the Special Funds for Jointly Building Universities of Tianjin (No. 280000307).

Abstract: 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 $ \mathrm{{ex}}_{}(n,H) $ is the maximum number of edges in an H-free graph on n vertices. Based on this definition, we define $ \mathrm{{ex}}_{_\mathcal {P}}(n,H) $ to restrict the graph classes to planar graphs, that is, $ \mathrm{{ex}}_{_\mathcal {P}}(n,H)=\max \{|E(G)|: G\in {\mathcal {G}} $, where $ {\mathcal {G}} $ is a family of all H-free planar graphs on n vertices. Obviously, we have $ \mathrm{{ex}}_{_{\mathcal {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 $ \mathrm{{ex}}_{_{\mathcal {P}}}(n,P_k) $ with $ k\in \{8,9\} $, where $ P_k $ is a path with k vertices.

Key words: Turán number, Extremal graph, Planar graph

中图分类号: