Planar Turán Numbers of Cubic Graphs and Disjoint Union of Cycles

期刊论文
发表日期：

2024年2月25日

查看全文

Yongxin Lan,
Yongtang Shi,
Zi-Xia Song

摘要

The planar Turán number of a graph H, denoted by $ex_{_\mathcal {P}}(n,H)$ $e x_{_{P}} (n, H)$ , is the maximum number of edges in a planar graph on n vertices without containing H as a subgraph. This notion was introduced by Dowden in 2016 and has attracted quite some attention since then; those work mainly focus on finding $ex_{_\mathcal {P}}(n,H)$ $e x_{_{P}} (n, H)$ when H is a cycle or Theta graph or H has maximum degree at least four. In this paper, we first completely determine the exact values of $ex_{_\mathcal {P}}(n,H)$ $e x_{_{P}} (n, H)$ when H is a cubic graph. We then prove that $ex_{_\mathcal {P}}(n,2C_3)=\lceil 5n/2\rceil -5$ $e x_{_{P}} (n, 2 C_{3}) = ⌈ 5 n / 2 ⌉ - 5$ for all $n\ge 6$ $n \geq 6$ , and obtain the lower bounds of $ex_{_\mathcal {P}}(n,2C_k)$ $e x_{_{P}} (n, 2 C_{k})$ for all $n\ge 2k\ge 8$ $n \geq 2 k \geq 8$ . Finally, we also completely determine the exact values of $ex_{_\mathcal {P}}(n,K_{2,t})$ $e x_{_{P}} (n, K_{2, t})$ for all $t\ge 3$ $t \geq 3$ and $n\ge t+2$ $n \geq t + 2$ .