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

doi:10.15960/j.cnki.issn.1007-6093.2025.02.018

运筹学学报（中英文） ›› 2025, Vol. 29 ›› Issue (2): 221-229.doi: 10.15960/j.cnki.issn.1007-6093.2025.02.018

{C₅, C₆}的平面Turán数

杜良丽¹, 王兵¹^,*()

1. 滁州学院数学与金融学院, 安徽滁州 239012

收稿日期:2022-06-22 出版日期:2025-06-15 发布日期:2025-06-12
通讯作者: 王兵 E-mail:wuyuwuyou@126.com
基金资助:
国家自然科学基金(12171066);安徽省自然科学基金(2108085MA13);安徽省高等学校自然科学研究一般项目(KJ2021B17)

Planar Turán numbers of {C₅, C₆}

Liangli DU¹, Bing WANG¹^,*()

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

Received:2022-06-22 Online:2025-06-15 Published:2025-06-12
Contact: Bing WANG E-mail:wuyuwuyou@126.com

摘要/Abstract

摘要：

设$\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-圈

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.

Key words: Turán number, planar graph, 5-cycle, 6-cycle

中图分类号:

O157.5

杜良丽, 王兵. {C₅, C₆}的平面Turán数[J]. 运筹学学报（中英文）, 2025, 29(2): 221-229.

Liangli DU, Bing WANG. Planar Turán numbers of {C₅, C₆}[J]. Operations Research Transactions, 2025, 29(2): 221-229.

图/表 11

图1

图2

图3

图4

图5

图6

图7

表1

图8

图9

图10

参考文献 9

1	Bondy J A , Murty U S R . Graph Theory[M]. New York: Springer, 2007.
2	Dowden C . Extremal C₄-free/C₅-free planar graphs[J]. Journal of Graph Theory, 2016, 83, 213- 230. doi: 10.1002/jgt.21991
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. doi: 10.1137/21M140657X
4	Lan Y X , Shi Y T , Song Z X . Extremal Theta-free planar graphs[J]. Discrete Mathematics, 2019, 342 (12): 111610. doi: 10.1016/j.disc.2019.111610
5	Ghosh D, Győri E, Paulos A, et al. Planar Turán Number of the Θ₆[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. doi: 10.1007/s00373-019-02055-w
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. doi: 10.37236/8255
9	兰永新, 史永堂, 宋梓霞. 图的平面Turán数和平面anti-Ramsey数[J]. 运筹学学报, 2021, 25 (3): 1- 17. doi: 10.15960/j.cnki.issn.1007-6093.2021.03.013

$ v(D_i) $	$ 30v(D_i)-13e(D_i)-30 $	计算依据
$ v(D_i)\geqslant5 $	$ \geqslant84-30=54 $	引理1
$ v(D_i)=4 $	$ \geqslant30\times4-13\times6-30=12 $	$ D_i\cong K_4, K_4^- $或$ C_4 $
$ v(D_i)=3 $	$ \geqslant30\times3-13\times3-30=21 $	$ D_i\cong K_3 $
$ v(D_i)=2 $	$ \geqslant30\times2-13\times1-30=17 $	$ D_i\cong K_2 $

[1]	卜月华, 陈雯雯, 朱俊蕾. 不含短圈的平面图的injective边染色[J]. 运筹学学报（中英文）, 2024, 28(4): 143-151.
[2]	卜月华, 张恒. 平面图的强边染色[J]. 运筹学学报, 2022, 26(2): 111-127.
[3]	李春梅, 王治文. Δ(G)=5的2-连通外平面图的邻点可区别全染色[J]. 运筹学学报, 2021, 25(4): 120-126.
[4]	兰永新, 史永堂, 宋梓霞. 图的平面Turán数和平面anti-Ramsey数[J]. 运筹学学报, 2021, 25(3): 200-216.
[5]	刘瑶. 带松弛条件的图的强边着色[J]. 运筹学学报, 2021, 25(2): 115-126.
[6]	陈敏, 杨建民, 张豪, 王依婷. 外平面图的弱完备染色[J]. 运筹学学报, 2021, 25(1): 132-136.
[7]	陈涛. 哈密尔顿平面图最小平衡二部划分的上界[J]. 运筹学学报, 2020, 24(3): 161-166.
[8]	陈洪玲, 王慧娟, 孙凤艳, 薛娟, 高红伟. 最大度大于等于7的平面图的线性荫度[J]. 运筹学学报, 2020, 24(3): 154-160.
[9]	罗朝阳, 孙林. 6-圈至多含一弦平面图的线性荫度[J]. 运筹学学报, 2019, 23(2): 113-119.
[10]	陈宏宇, 谭香. 不含5-圈和相邻4-圈的平面图的线性2-荫度的一个上界[J]. 运筹学学报, 2019, 23(1): 104-110.
[11]	张欣, 刘维婵. 1-平面图及其子类的染色[J]. 运筹学学报, 2017, 21(4): 135-152.
[12]	张欣, 刘桂真, 吴建良. 1-平面图的线性荫度[J]. 运筹学学报, 2011, 15(3): 38-44.

{C₅, C₆}的平面Turán数

Planar Turán numbers of {C₅, C₆}

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 11

参考文献 9

相关文章 12

编辑推荐

Metrics

本文评价