论文

{C5, C6}的平面Turán数

展开
  • 1. 滁州学院数学与金融学院, 安徽滁州 239012
王兵   E-mail: wuyuwuyou@126.com

收稿日期: 2022-06-22

  网络出版日期: 2025-06-12

基金资助

国家自然科学基金(12171066);安徽省自然科学基金(2108085MA13);安徽省高等学校自然科学研究一般项目(KJ2021B17)

版权

运筹学学报编辑部, 2025, 版权所有,未经授权,不得转载。

Planar Turán numbers of {C5, C6}

Expand
  • 1. School of Mathematics and Finance, Chuzhou University, Chuzhou 239012, Anhui, China

Received date: 2022-06-22

  Online published: 2025-06-12

Copyright

, 2025, All rights reserved. Unauthorized reproduction is prohibited.

摘要

$\mathcal{H}$是一个图族。$\mathcal{H}$的平面Turán数, 记为$\text{ex}_{\mathcal{P}}(n,\mathcal{H})$, 表示不包含$\mathcal{H}$中任一个图的n阶平面图的最大边数。本文研究图的特定子图-三角块的划分, 在该划分基础上对每个三角块对图G的顶点、边和面的贡献计数。结合平面图的结构特性并通过双向计数和归纳技巧得到如下结果: 设G是禁用$\{C_5,C_6\}$的连通n阶平面图, 如果$n \geq 14$, 则$e(G)\leq\frac{30n-84}{13}$。在此基础上, 构造了无穷多个达到该界值的极图。

关键词: Turán数; 平面图; 5-圈; 6-圈

本文引用格式

杜良丽, 王兵 . {C5, C6}的平面Turán数[J]. 运筹学学报, 2025 , 29(2) : 221 -229 . DOI: 10.15960/j.cnki.issn.1007-6093.2025.02.018

Abstract

Let $\mathcal{H}$ be a family of graphs. The planar Turán number of $\mathcal{H}$, denoted by ex$_{\mathcal{P}}(n,\mathcal{H})$, is the maximum number of edges over all planar graphs on n vertices that do not contain any $H\in\mathcal{H}$ as a subgraph. In this paper, we partition the graph into some specific subgraphs called as triangle blocks. Based on the partition, we calculate the contribution of each triangle block to the vertex, edge and face to graph G, respectively. Considered the structure of plane graph and by double-counting techniques and induction on the order of G, we obtained the following result: Let G be a connected $\{C_5,C_6\}$-free plane graph on n vertices, if $n\geq14$, then $e(G)\leq\frac{30n-84}{13}$. We also give infinitely many graphs which attain these bounds.

参考文献

1 Bondy J A , Murty U S R . Graph Theory[M]. New York: Springer, 2007.
2 Dowden C . Extremal C4-free/C5-free planar graphs[J]. Journal of Graph Theory, 2016, 83, 213- 230.
3 Ghosh D , Gy?ri E , Martin R R , et al. Planar Turán Number of the 6-Cycle[J]. SIAM Journal on Discrete Mathematics, 2022, 36 (3): 2028- 2050.
4 Lan Y X , Shi Y T , Song Z X . Extremal Theta-free planar graphs[J]. Discrete Mathematics, 2019, 342 (12): 111610.
5 Ghosh D, Gy?ri E, Paulos A, et al. Planar Turán Number of the Θ6[EB/OL]. [2022-06-21]. arxiv: 2006.00994v1.
6 Lan Y X , Shi Y T . Planar Turán numbers of short paths[J]. Graphs and Combinatorics, 2019, 35 (5): 1035- 1049.
7 Fang L F , Wang B , Zhai M Q . Planar Turán number of intersecting triangles[J]. Discrete Mathematics, 2020, 345 (5): 112794.
8 Lan Y X , Shi Y T , Song Z X . Extremal H-free planar graphs[J]. Electronic Journal of Combinatorics, 2019, 26 (2): 2.11.
9 兰永新, 史永堂, 宋梓霞. 图的平面Turán数和平面anti-Ramsey数[J]. 运筹学学报, 2021, 25 (3): 1- 17.
文章导航

/