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

Abstract

The planar Turán number of a graph H, denoted by $ex_{_\mathcal {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)$ 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)$ when H is a cubic graph. We then prove that $ex_{_\mathcal {P}}(n,2C_3)=\lceil 5n/2\rceil -5$ for all $n\ge 6$, and obtain the lower bounds of $ex_{_\mathcal {P}}(n,2C_k)$ for all $n\ge 2k\ge 8$. Finally, we also completely determine the exact values of $ex_{_\mathcal {P}}(n,K_{2,t})$ for all $t\ge 3$ and $n\ge t+2$.

Appendix

Proof of Lemma 2.1

Let G be given as in the statement. To establish the desired result, we first assume that there exists a vertex, say $v_1\in V(G)$, such that $v_1$ belongs to no triangle in G. Then $e(G[N_G[v_1]])=3$. Let $N_G(v_1)=\{v_2,v_3,v_4\}$ and $A=V(G){{\setminus }}N_G[v_1]$. Then $e_G(N_G(v_1),A)=6$ because G is a cubic graph. Hence, $e(G[A])=e(G)-e(G[N_G[v_1]])-e_G(N_G(v_1),A)=3$, which implies that $G[A]\in \{K_{1,3},P_{4},K_3\cup K_1\}$. Since G is cubic, we see $G[A]\ne K_3\cup K_1$ by the planarity of G. That is either $G[A]= K_{1,3}$ or $G[A]= P_{4}$. If $G[A]= K_{1,3}$ and $x\in A$ is the center of $K_{1,3}$, then $G{{\setminus }}\{v_1,x\} = C_6$ and so $G=G_1$. So we next assume that $G[A]= P_{4}$. Let G[A] be a path with vertices $v_5,v_6,v_7,v_8$ in order. We claim that $v_6$ and $v_7$ have no common neighbour in G. Suppose $v_6$ and $v_7$ have a common neighbour, say $v_2$. Then $N_G(v_3)=N_G(v_4)=\{v_1,v_5,v_8\}$ because G is a cubic graph. But then G has a $K_{3,3}$-minor with one part $\{v_2,v_3,v_4\}$ and the other part $\{v_1,\{v_5,v_6\},\{v_7,v_8\}\}$, a contradiction. Thus, $v_6$ and $v_7$ have no common neighbour in G. Without loss of generality, we may assume that $v_6v_2,v_7v_3\in E(G)$. Notice that $N_G(v_4)=\{v_1,v_5,v_8\}$ because G is a cubic graph. Then we see that either $v_5v_2\in E(G)$ or $v_5v_3\in E(G)$. If $v_5v_3\in E(G)$, then $v_8v_2\in E(G)$ and so G contains a $K_{3,3}$-minor with one part $\{v_2,v_3,v_4\}$ and the other part $\{v_1,\{v_5,v_6\},\{v_7,v_8\}\}$, a contradiction. Hence, $v_5v_2\in E(G)$ and so $v_8v_3\in E(G)$, which implies that $G=G_2$.

Next we assume that every vertex in G belongs to at least one triangle. We claim that there must exist a vertex such that it belongs to two triangles. Suppose that every vertex in G belongs to exactly one triangle. Let $v_1\in V(G)$. Then $G[N_G[v_1]]= K_1+(K_2\cup K_1)$. Let $A=V(G){{\setminus }}N_G[v_1]$. Then $e_G(N_G(v_1),A)=4$ because G is a cubic graph. Hence, $e(G[A])=e(G)-e(G[N_G[v_1]])-e_G(N_G(v_1),A)=4$, which implies that either $G[A]= C_4$ or $G[A]= K_1+(K_2\cup K_1)$. If $G[A]= C_4$, there exist two vertices in A which does not belong to any triangle, a contradiction. If $G[A]= K_1+(K_2\cup K_1)$, then there exists one vertex such that it belongs to either two triangles or no triangle, a contradiction. Thus, there must exist a vertex belonging to two triangles. Assume that $v_1$ belongs to two triangles in G. Since G is $K_4$-free, we have $G[N_G[v_1]]= K_4^-$. Let $A=V(G){{\setminus }}N_G[v_1]$. Then $e_G(N_G(v_1),A)=2$ because G is a cubic graph. Hence, $e(G[A])=e(G)-e(G[N_G[v_1]])-e_G(N_G(v_1),A)=5$, which implies that $G[A]= K_4^-$. Thus, $G=G_3$. $\square$

Proof of Lemma 2.2

Let G be given as in the statement. Let v be an arbitrary vertex in G and $V(G){{\setminus }}N_G[v]=\{v_1,v_2\}.$ Then $v_1v_2\in E(G)$, else $N_G(v_i)=N_G(v)$ for any $i\in [2]$, which yields that $G\cong K_{3,3}$. Since G is a cubic graph, we see that $|N_{N_G(v)(v_i)}|=2$ for any $i\in [2]$, and $N_{N_G(v)}(v_1)\notin N_{N_G(v)}(v_2)$. Hence, $G[N_G(v)]\cong K_2\cup K_1$, which implies that G is the graph given in Figure 2. $\square$