Research Article

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.

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.

Cite this article

Liangli DU, Bing WANG . Planar Turán numbers of {C5, C6}[J]. Operations Research Transactions, 2025 , 29(2) : 221 -229 . DOI: 10.15960/j.cnki.issn.1007-6093.2025.02.018

References

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.
Outlines

/