Extremal graphs for the odd prism

Xiaocong He1, Yongtao Li1,2,111Corresponding author. Email addresses:
<EMAIL_ADDRESS>(Xiǎocōng Hè<EMAIL_ADDRESS>(Yǒngtāo Lǐ),
<EMAIL_ADDRESS>(Lìhuá Féng). This work was supported by NSFC (Nos. 12271527,
12071484, 11931002), Natural Science Foundation of Hunan Province (Nos.
2020JJ4675, 2021JJ40707) and the Fundamental Research Funds for the Central
Universities of Central South University (Grant No. 2021zzts0034)., Lihua
Feng1

1School of Mathematics and Statistics, HNP-LAMA, Central South University

Changsha, Hunan, 410083, PR China

2School of Mathematics, Hunan University

Changsha, Hunan, 410082, P.R. China

Abstract: The Turán number $\operatorname{ex}(n,H)$ of a graph $H$ is the
maximum number of edges in an $n$-vertex graph which does not contain $H$ as a
subgraph. The Turán number of regular polyhedrons was widely studied in a
series of works due to Simonovits. In this paper, we shall present the Turán
number of the prism $C_{2k+1}\square P_{2}$, which is defined as the Cartesian
product of the odd cycle $C_{2k+1}$ and the path $P_{2}$. Applying a deep
theorem of Simonovits and a stability result of Yuan [European J. Combin. 104
(2022)], we shall determine the exact value of
$\operatorname{ex}(n,C_{2k+1}\square P_{2})$ for every $k\geq 1$ and
sufficiently large $n$, and we also characterize the extremal graphs.
Moreover, in the case of $k=1$, motivated by a recent result of Xiao, Katona,
Xiao and Zamora [Discrete Appl. Math. 307 (2022)], we will determine the exact
value of $\operatorname{ex}(n,C_{3}\square P_{2})$ for every integer $n$, not
only for sufficiently large $n$.

Keywords: Turán number, Extremal graphs, Cartesian product.

AMS classification: 05C35.

##  1 Introduction

In this paper, all graphs considered are undirected, finite and contain
neither loops nor multiple edges. Let $G$ be such a graph, the vertex set of
$G$ is denoted by $V(G)$, the edge set of $G$ by $E(G)$, and the number of
edges in $G$ by $e(G)$. Let $K_{n}$ be the complete graph on $n$ vertices, and
$K_{s,t}$ be the complete bipartite graph with parts of sizes $s$ and $t$. We
write $C_{n}$ and $P_{n}$ for the cycle and path on $n$ vertices,
respectively. Let $r\geq 2$ and $n\geq 2$ be integers. The Turán graph
$T_{r}(n)$ is an $n$-vertex complete $r$-partite graph with each part of size
$n_{i}$ such that $|n_{i}-n_{j}|\leq 1$ for all $1\leq i,j\leq r$, that is,
$n_{i}$ equals $\lfloor{n}/{r}\rfloor$ or $\lceil{n}/{r}\rceil$. Sometimes, we
call $T_{r}(n)$ the balanced complete $r$-partite graph. In particular, we
have $T_{2}(n)=K_{\lfloor\frac{n}{2}\rfloor,\lceil\frac{n}{2}\rceil}$.

Denote by $G_{1}\cup G_{2}$ the vertex-disjoint union of two graphs $G_{1}$
and $G_{2}$. For simplicity, we write $kG$ for the vertex-disjoint union of
$k$ copies of $G$. Denote by $G_{1}\otimes G_{2}$ the graph obtained from
$G_{1}\cup G_{2}$ by joining each vertex of $G_{1}$ to each vertex of $G_{2}$.
For a vertex $v\in V(G)$, and a subgraph $H\subseteq G$ (possibly $v\in
V(H)$), we use $N_{H}(v)$ to denote the set of neighbors of $v$ in $V(H)$, and
use $d_{H}(v)$ to denote $|N_{H}(v)|$. We denote the minimum degree of $G$ by
$\delta(G)$, the complement of $G$ by $\overline{G}$. In particular,
$\overline{K}_{n}$ is the empty graph, which is also called an independent set
on $n$ vertices. The chromatic number of $G$, denoted by $\chi(G)$, which is
the minimum integer $s\in\mathbb{N}^{*}$ such that there exists a coloring of
the vertex set $V(G)$ with $s$ colors and the adjacent vertices have different
colors. For example, $\chi(C_{2k+1})=3$. The independence number $\alpha(G)$
is the maximum cardinality of an independent set in $G$.

###  1.1 Turán number of regular polyhedrons

Let $G$ and $H$ be two simple graphs. We say that $G$ is $H$-free if it does
not contain a subgraph isomorphic to $H$. For example, every bipartite graph
is triangle-free. The Turán number of a graph $H$, denoted by
$\operatorname{ex}(n,H)$, is the maximum number of edges in an $n$-vertex
$H$-free graph. Moreover, an $n$-vertex $H$-free graph with maximum number of
edges is called an extremal graph for $H$. In general, it is possible that
there are many (not only one) extremal graphs for a graph $H$. For instance,
our result in this article shares this phenomenon.

The problem of determining Turán numbers is one of the cornerstones of graph
theory. Observe that the balanced complete $r$-partite graph $T_{r}(n)$ is
$K_{r+1}$-free. In 1941, Turán [44] proved
$\mathrm{ex}(n,K_{r+1})=e(T_{r}(n))$. Moreover, $T_{r}(n)$ is the unique
$K_{r+1}$-free graph attaining the maximum number of edges. In particular, for
$r=2$, it gives

$\mathrm{ex}(n,K_{3})=\lfloor{n^{2}}/{4}\rfloor,$ (1)

which was early proved by Mantel [35]; see, e.g., the monograph [3, p. 294]
for alternative proofs and extensions, and the surveys [26, 42] for more
related results.

After Turán [44] determined the extremal graphs of the tetrahedron $K_{4}$, he
asked the following analogous problem: Determining the Turán number of a graph
consisting of the vertices and edges of a regular polyhedron. For example, the
cube $Q_{8}$, the octahedron $O_{6}$, the dodecahedron $D_{20}$ and the
icosahedron $I_{12}$; see the following Figure 1.

Figure 1: The five regular polyhedrons

The Turán problem involving regular polyhedrons was widely studied in the
literature; see, e.g., [18, 37, 25] for the cube $Q_{8}$, [19] for the
octahedron $O_{6}$, [39] for the dodecahedron $D_{20}$, and [40] for the
icosahedron $I_{12}$. In particular, although Erdős and Simonovits [18] showed
that $\mathrm{ex}(n,Q_{8})\leq Cn^{8/5}$ for some constant $C>0$, the lower
bound on the Turán number of $Q_{8}$ remains open. Motivated by the above
results, we shall consider the Turán problem of the prism, which can be viewed
as a variant graph of the cube $Q_{8}$.

The celebrated Erdős–Stone–Simonovits Theorem [16, 17] states that

$\displaystyle\operatorname{ex}(n,H)=\left(1-\frac{1}{\chi(H)-1}\right)\binom{n}{2}+o(n^{2}),$
(2)

where $\chi(H)$ is the chromatic number of $H$. This result determines the
asymptotic value of $\operatorname{ex}(n,H)$ for every non-bipartite graph
$H$, and it reduces to $\mathrm{ex}(n,H)=o(n^{2})$ for every bipartite graph
$H$. At the first glance, the formula (2) gives a satisfactory answer to the
problem of estimating $\mathrm{ex}(n,H)$. Furthermore, it is an important
problem in extremal combinatorics to obtain more accurate bound on the error
term $o(n^{2})$. In particular, one of the central problems is to determine
the exact Turán number for a graph $H$.

There are many elegant results on finding the exact value of
$\mathrm{ex}(n,H)$ for a specific graph $H$. For example, the earliest result
due to Mantel [35] provided $\operatorname{ex}(n,C_{3})=\lfloor
n^{2}/4\rfloor$. Erdős, Füredi, Gould and Gunderson [14], Chen, Gould, Pfender
and Wei [7] determined the exact Turán number for intersecting triangles and
cliques, respectively. Liu [33] determined the Turán number for the edge-blow-
ups of cycles and a large class of trees, and Ni, Kang, Shan and Zhu [36]
investigated the edge-blow-ups of keyrings. In 2022, Yuan [50] studied the
Turán number and extremal graphs for the edge-blow-ups of complete graphs and
complete bipartite graphs. Applying the stability theorem of Erdős and
Simonovits, Hou, Qiu and Liu [28, 29], and Yuan [48] independently determined
the Turán number for flower graphs. Moreover, Dzido [11], Dzido and
Jastrzebski [12], and Yuan [49] determined the Turán number for wheels. In
2022, Xiao, Katona, Xiao and Zamora [45], and Yuan [51] characterized the
extremal graphs for the power of a path.

###  1.2 The prism and Cartesian product

Apart from the five regular polyhedrons in Figure 1, there are two well-known
polyhedrons, called the pyramid and prism; see Figure 2. In fact, it is easy
to observe that the pyramid is actually a wheel graph, which was studied by
Dzido [11], Dzido and Jastrzebski [12] and Yuan [49]. Differing from the study
of the pyramid (wheel), in this paper, we shall pay attention to the Turán
number of the prism, and characterize the extremal graphs.

Figure 2: The quadrangular pyramid and triangular prism

On the other hand, one can consider the prism from the perspective of
Cartesian product of graphs. Recall that the Cartesian product of graphs $G$
and $F$, denoted by $G\square F$, has vertex set $V(G)\times V(F)$, in which
two distinct vertices $(g_{1},f_{1})$ and $(g_{2},f_{2})$ are adjacent in
$G\square F$ if either $g_{1}=g_{2}$ and $f_{1}f_{2}\in E(F)$, or
$f_{1}=f_{2}$ and $g_{1}g_{2}\in E(G)$.

In 2022, Bradač, Janzer, Sudakov and Tomon [4] studied the Turán number of the
grid $P_{t}\square P_{t}$, where $P_{t}$ is the path on $t$ vertices. More
precisely, they proved that for each integer $t\geq 2$, there exist positive
numbers $C_{1}$ and $C_{2}$ depending only on $t$ such that

$C_{1}n^{3/2}\leq\mathrm{ex}(n,P_{t}\square P_{t})\leq C_{2}n^{3/2}.$

In our paper, we shall consider the Turán number for the Cartesian product of
an odd cycle and a path. Recall that $C_{2k+1}$ is the cycle on $2k+1$
vertices. Observe that the odd prism can be written as the Cartesian product
$C_{2k+1}\square P_{2}$. For example, the triangular prism is equal to
$C_{3}\square P_{2}$; see, e.g., Figure 2. As promised, we shall study the
Turán number of the prism $C_{2k+1}\square P_{2}$. First of all, we observe
that $\chi(C_{2k+1}\square P_{2})=3$. By Erdős–Stone–Simonovits’ theorem in
(2), one can get an asymptotic value as below

$\operatorname{ex}(n,C_{2k+1}\square P_{2})=\frac{n^{2}}{4}+o(n^{2}).$

Furthermore, one natural problem is to refine the error term and determine the
exact Turán number of $C_{2k+1}\square P_{2}$. Our result in this paper solves
this problem and study the exact value of $\operatorname{ex}(n,C_{2k+1}\square
P_{2})$. Moreover, we also characterize the extremal graphs for
$C_{2k+1}\square P_{2}$.

###  1.3 Main results

The first result in this paper can be stated as below.

######  Theorem 1.

Let $k\geq 1$ be fixed and $n$ be sufficiently large. Then

$\emph{ex}(n,C_{2k+1}\square
P_{2})=\max\limits_{n_{a}+n_{b}=n}\left\\{n_{a}(1+n_{b})+\frac{1}{2}(j^{2}-3j):j\in\\{0,1,2\\},j\equiv
n_{a}(\mathrm{mod}~{}{3})\right\\}.$

Moreover, all extremal graphs for $C_{2k+1}\square P_{2}$ are of the form of a
complete bipartite graph $K_{n_{a},n_{b}}$ with an extremal graph for $P_{4}$
added to the part of size $n_{a}$.

There are a few kinds of graphs $H$ for which $\mathrm{ex}(n,H)$ are known
exactly for all integers $n$, including cliques, matchings, paths, odd cycles
and some other special graphs. To be more specific, Turán [44] determined the
value of $\mathrm{ex}(n,K_{r+1})$ for all $n$, Erdős and Gallai [15]
determined $\mathrm{ex}(n,P_{k})$ and $\mathrm{ex}(n,M_{2k})$, where $M_{2k}$
is the matching on $2k$ vertices. Füredi and Gunderson [22] determined
$\mathrm{ex}(n,C_{2k+1})$ for all $n$ and $k\geq 2$. Bushaw and Kettle [5]
determined $\mathrm{ex}(n,kP_{3})$ for all $n\geq 7k$, and Later, Campos and
Lopes [6], Yuan and Zhang [46], independently determined the value
$\mathrm{ex}(n,kP_{3})$ for all integers $n$ and $k$. Moreover, Bielak and
Kieliszek [2] determined $\mathrm{ex}(n,2P_{5})$ for all $n$, which was also
proved by Yuan and Zhang [47] independently. In addition, Lan, Qin and Shi
[32] determined $\mathrm{ex}(n,2P_{7})$ for all $n$.

For the triangular prism in Figure 2, that is, the case $k=1$ in Theorem 1, we
will use a different method, and get rid of the condition that $n$ is
sufficiently large. More precisely, we will determine
$\mathrm{ex}(n,C_{3}\square P_{2})$ for all $n$, and present all $C_{3}\square
P_{2}$-free graphs on $n$ vertices with maximum number of edges. Our results
will be presented in the following two theorems, where we provide the Turán
number first, and give the corresponding extremal graphs later.

######  Theorem 2.

The maximum number of edges in an $n$-vertex $C_{3}\square P_{2}$-free graph
$(n\neq 5)$ is

$\operatorname{ex}(n,C_{3}\square P_{2})=\left\\{\begin{aligned}
&\left\lfloor\frac{n^{2}}{4}\right\rfloor+\left\lfloor\frac{n-1}{2}\right\rfloor,~{}\text{if}~{}n\equiv
1,2,3~{}(\bmod~{}6),\\\
&\left\lfloor\frac{n^{2}}{4}\right\rfloor+\left\lceil\frac{n}{2}\right\rceil,~{}\text{otherwise}.\end{aligned}\right.$

Before showing the extremal graphs in Theorem 2, we need to fix the following
notation, which originally appears in Xiao, Katona, Xiao and Zamora [45]. Let
$K_{i,n-i}$ be the complete bipartite graph on parts $X$ and $Y$ with $|X|=i$
and $|Y|=n-i$, respectively. On the one hand, if $3\mid i$, then embedding
$\frac{i}{3}$ vertex-disjoint triangles in the class $X$ and keeping the class
$Y$ unchanged, we get a new graph on $n$ vertices, and denoted by $H^{i}_{n}$.
On the other hand, if $3\centernot\mid i$, then choosing an integer
$j\in[1,i]$ such that $3\mid(i-j)$, we define $F^{i,j}_{n}$ as the graph
obtained from $K_{i,n-i}$ by embedding a star on $j$ vertices, and
$\frac{i-j}{3}$ vertex-disjoint triangles in the class $X$, where the star is
disjoint from any triangle. Clearly, one can observe that both $H_{n}^{i}$ and
$F_{n}^{i,j}$ are $C_{2k+1}\square P_{2}$-free for any possible $i$ and $j$.
In addition, for small integer $n$, we need to introduce three exceptional
graphs $G_{1},G_{2}$ and $G_{3}$; see Figure 3.

$v_{3}$$v_{1}$$v_{2}$$v_{5}$$v_{6}$$v_{4}$$G_{1}$$v_{5}$$v_{3}$$v_{6}$$v_{4}$$v_{1}$$v_{2}$$v$$G_{2}$$v_{5}$$v_{3}$$v_{6}$$v_{4}$$x$$v_{1}$$v_{2}$$y$$G_{3}$
Figure 3: The graphs $G_{1},G_{2}$ and $G_{3}$.

The extremal graphs for $C_{3}\square P_{2}$ are presented in the following
tables.

######  Theorem 3.

For $n\geq 6$, the extremal graphs for $C_{3}\square P_{2}$ are the following
ones.

order $n$ | 6 | 7 | 8
---|---|---|---
extremal graphs | $G_{1},H_{6}^{3}$ |  $G_{2},F_{7}^{4,1}\\!,F_{7}^{4,4}\\!,H_{7}^{3}$ |  $G_{3},F_{8}^{4,1}\\!,F_{8}^{4,4}\\!,F_{8}^{5,2}\\!,F_{8}^{5,5}$

Moreover, for $n\geq 9$, we have the following extremal graphs.

order $n~{}(\mathrm{mod}~{}6)$ | 0 | 1 | 2 | 3 | 4 | 5
---|---|---|---|---|---|---
extremal graphs | $H_{n}^{{\frac{n}{2}}}$ | $F_{n}^{\lceil\\!\frac{n}{2}\\!\rceil,j}\\!,H_{n}^{\lfloor\\!{\frac{n}{2}}\\!\rfloor}$ | $F_{n}^{{\frac{n}{2}},j}\\!,F_{n}^{{\frac{n}{2}}+1,j}$ | $F_{n}^{\lceil\\!\frac{n}{2}\\!\rceil,j}\\!,H_{n}^{\lceil\\!{\frac{n}{2}}\\!\rceil+1}$ | $H_{n}^{{\frac{n}{2}}+1}$ | $H_{n}^{\lceil\\!{\frac{n}{2}}\\!\rceil}$

where $j$ can be chosen as any possible integer satisfying $1\leq j\leq i$ and
$3\mid(i-j)$.

Outline of the paper. The rest of this paper is organized as follows. In
Section 2, we shall present some preliminaries, including the Turán-type
results on paths, and a deep structure theorem of Simonovits for graphs whose
decomposition family contains a linear forest. In Section 3, we will give the
proof of Theorem 1. In Section 4, in order to determine the $n$-vertex
extremal graphs for the triangular prism $C_{3}\square P_{2}$ for every $n\geq
6$, we will provide some lemmas for our purpose. Later, the proofs of Theorems
2 and 3 are given in Section 5, respectively. Finally, some open problems are
proposed in Section 6.

##  2 Preliminaries

###  2.1 The Turán-type results for paths

To begin with, we need to introduce a result of Erdős and Gallai [15].

######  Theorem 4 (Erdős and Gallai [15]).

The maximum number of edges in an $n$-vertex $P_{k}$-free graph is
${n(k-2)\over 2}$, that is, $\operatorname{ex}(n,P_{k})\leq{n(k-2)\over 2}$,
with equality if and only if $(k-1)|n$ and the graph is a vertex disjoint
union of ${n\over k-1}$ copies of $K_{k-1}$.

Note that the bound in Theorem 4 is sharp only in the case $(k-1)|n$.
Furthermore, for the general cases, say $n=(k-1)t+r$, this bound was refined
by Faudree and Schelp [27], and independently by Kopylov [31] using a
different method.

######  Theorem 5 (Faudree and Schelp [27], Kopylov [31]).

Let $n=(k-1)t+r$ with $t\geq 1$ and $0\leq r\leq k-2$. Then

$\operatorname{ex}(n,P_{k})=t\binom{k-1}{2}+\binom{r}{2}.$

Moreover, each $n$-vertex extremal graph for $P_{k}$ is isomorphic to either

$tK_{k-1}\cup K_{r}$

or

$(t-s-1)K_{k-1}\cup\left(K_{\frac{k-2}{2}}\otimes\overline{K}_{\frac{k}{2}+s(k-1)+r}\right)$

for some $s\in[0,t-1]$ when $k$ is even and
$r\in\\{\frac{k}{2},\frac{k-2}{2}\\}$.

In this paper, we shall use the case $k=4$.

######  Corollary 6.

Let $G$ be a $P_{4}$-free graph on $n$ vertices. Then

$e(G)\leq n+\frac{1}{2}(j^{2}-3j),$

where $j\in\\{0,1,2\\}$ and $j\equiv n(\mathrm{mod}~{}3)$. More precisely,
(a) if $n=3t$, then $e(G)\leq 3t$, equality holds if and only if $G=tC_{3}$;
(b) if $n=3t+1$, then $e(G)\leq 3t$, equality holds if and only if

$G\in\\{tC_{3}\cup K_{1}\\}\cup\\{(t-\ell-1)C_{3}\cup
K_{1,3\ell+3}:0\leq\ell\leq t-1\\}$

(c) if $n=3t+2$, then $e(G)\leq 3t+1$, equality holds if and only if

$G\in\\{tC_{3}\cup K_{2}\\}\cup\\{(t-\ell-1)C_{3}\cup
K_{1,3\ell+4}:0\leq\ell\leq t-1\\}.$

Recently, the stability result for (connected) $P_{k}$-free graphs was
successively studied by Füredi, Kostochka, Luo and Verstraëte [23, 24], and Ma
and Ning [34]. To prove Theorem 1, we need to apply the following variant due
to Yuan [51].

######  Lemma 7 (Yuan [51]).

Let $c$ be a positive integer and $n$ be sufficiently large. Given an
$n$-vertex $P_{k}$-free graph $G$ with $e(G)\geq\emph{ex}(n,P_{k})-c$. Let
$\ell=\min\\{n/(16c),n/(2k-2)\\}$ and $t=\lfloor\frac{k}{2}\rfloor\geq 3$. If
$k$ is odd, then $G$ contains a copy of $\ell K_{k-1}$. If $k$ is even, then
$G$ contains either a copy of $\ell K_{k-1}$ or a copy of $K_{1,\ell}$.

Note that the result also holds for $t=2$.

###  2.2 A deep theorem of Simonovits

The decomposition family of a graph was firstly introduced by Simonovits [41],
and it was used to study the Turán numbers of non-bipartite graphs. For a
fixed graph $H$, the error term $o(n^{2})$ in (2) can be refined by the
decomposition family of $H$. Moreover, the decomposition family of a non-
bipartite graph can help us to determine the finer structure of its extremal
graphs. Now let us give the definition of the decomposition family of a graph.

######  Definition 8 (Simonovits).

Given a graph $L$ with $\chi(L)=p+1\geq 2$. Let $\mathcal{M}(L)$ be the family
of minimal graphs $M$ satisfying the following: there exists an integer $t\geq
1$ depending on $L$ such that $L\subseteq(M\cup\overline{K}_{t})\otimes
T_{p-1}((p-1)t)$. We call $\mathcal{M}(L)$ the decomposition family of $L$.

In other words, a graph $M$ belongs to $\mathcal{M}(L)$ if putting a copy of
$M$ (but not any of its proper subgraphs) into one vertex part of a large
$p$-partite Turán graph $T_{p}(pt)$ will lead to a copy of $L$. For example,
we have $\mathcal{M}(sK_{r+1})=\\{sK_{2}\\}$ for each $s\geq 1$ and $r\geq 2$.
Moreover, for the dodecahedron $D_{20}$ and icosahedron $I_{12}$ in Figure 1,
it was proved in [39, 40] that $\mathcal{M}(D_{20})=\\{6K_{2}\\}$ and
$\mathcal{M}(I_{12})=\\{P_{6}\\}$, respectively. In addition, for the wheels
(the pyramid) in Figure 2, it can be seen in [49] that
$\mathcal{M}(W_{2k+1})=\\{K_{1,k},C_{2k}\\}$ and
$\mathcal{M}(W_{2k})=\\{K_{2}\\}$, since $\chi(W_{2k})=4$ and
$\chi(W_{2k}-e)=3$ for each edge $e$ in the cycle.

The following lemma follows immediately from the definition.

######  Lemma 9.

Given a graph $L$ with $\chi(L)=p+1\geq 2$. If $G$ is a graph obtained from
the $p$-partite Turán graph $T_{p}(n)$ by embedding an extremal graph for
$\mathcal{M}(L)$ into one part, then $G$ is $L$-free. Consequently, we get
$\mathrm{ex}(n,L)\geq
e(T_{p}(n))+\mathrm{ex}(\lceil\frac{n}{p}\rceil,\mathcal{M}(L))$.

In the proof of Theorem 1, we will use the following theorem, which attributes
to a deep theorem of Simonovits [39, p. 371]. Roughly speaking, it states that
if the decomposition family $\mathcal{M}(L)$ contains a linear forest (a graph
in which each component is a path), then the extremal graphs for $L$ have a
very simple and symmetric structure.

######  Theorem 10 (Simonovits [39]).

Let $L$ be a given graph with $p=\chi(L)-1$. If the decomposition family
$\mathcal{M}(L)$ contains a linear forest, then there exist $r=r(L)$ and
$n_{0}=n_{0}(r)$ such that if $n\geq n_{0}$, then each $n$-vertex extremal
graph $G$ for $L$ belongs to the family of graphs satisfying the following.
(a) After deleting at most $r$ vertices of $G$, the remaining graph
$G^{\prime}$ satisfies

$G^{\prime}=G^{1}\otimes G^{2}\otimes\cdots\otimes G^{p},$

where the graph $G^{i}$ satisfies $||V(G^{i})|-n/p|\leq r$ for each $1\leq
i\leq p$.
(b) For each $1\leq i\leq p$, the graph $G^{i}$ consists of vertex disjoint
copies of non-isomorphic connected graphs $H^{j}_{i}s$ with
$|V(H_{i}^{j})|\leq r$ such that any two copies, say $F_{1}$ and $F_{2}$, of
$H_{i}^{j}$s are symmetric subgraphs in $G$: there exists an isomorphism
$\psi:F_{1}\rightarrow F_{2}$ such that for every $x\in V(F_{1})$ and $y\in
G-F_{1}-F_{2}$, $xy$ is an edge if and only if $\psi(x)y$ is an edge.

Theorem 10 can benefit us to characterize the approximate structure of all
extremal graphs for the prism $C_{2k+1}\square P_{2}$. We remark that this
theorem was also used by Yuan [51] for treating the Turán problem of the power
of a path. In particular, we refer the readers to [50] for graphs $L$ whose
decomposition family $\mathcal{M}(L)$ contains a matching.

##  3 Proof of Theorem 1

The following lemma is simple, but it plays an important role in our proof.

######  Lemma 11.

The decomposition family $\mathcal{M}(C_{2k+1}\square P_{2})=\\{P_{4}\\}$.

###### Proof.

Clearly, the chromatic number $\chi(C_{2k+1}\square P_{2})=3$. Observe that
there are exactly two copies of $C_{2k+1}$ in $C_{2k+1}\square P_{2}$.
Moreover, every maximal independent set of $C_{2k+1}\square P_{2}$ consists of
a $k$-vertex independent set of one $C_{2k+1}$ and a $k$-vertex independent
set of the another such that there are no adjacent vertices between these two
sets. Let $I$ be any maximal independent set of $C_{2k+1}\square P_{2}$. It is
easy to see that the subgraph of $C_{2k+1}\square P_{2}$ induced by vertices
outside of $I$ consists of $P_{4}$ with some isolated vertices. By the
definition of decomposition family, we have $\mathcal{M}(C_{2k+1}\square
P_{2})=\\{P_{4}\\}$. ∎

######  Lemma 12.

Let $G=G^{1}\otimes G^{2}$ with $|V(G^{i})|=n_{i}\geq 2k+1$ for $i=1,2$.
(a) Let $G^{\prime}$ be the graph obtained from $G$ by adding a new vertex $y$
with $|N_{G^{i}}(y)|\geq 3$ for $i=1,2$. If $G^{1}\cup G^{2}$ has an edge
incident with $N_{G}(y)$, then $G^{\prime}$ contains a copy of
$C_{2k+1}\square P_{2}$.
(b) If both $G^{1}$ and $G^{2}$ contain an edge, then $G$ contains a copy of
$C_{2k+1}\square P_{2}$.

$x$$y$$v_{1}$$v_{2}$$~{}~{}v_{2k-2}$$v_{2k-1}$$v_{2k}$$u_{1}$$u_{2}$$u_{2k-2}$$u_{2k-1}$$u_{2k}$$\ldots$$\cdots$$\ldots$$\ldots$$\ldots$$\ldots$$e$$G^{1}$$G^{2}+y$
Figure 4: The graph $G^{\prime}$.

###### Proof.

(a) Without loss of generality, we assume that $G^{1}$ contains an edge $e$,
which is incident with $x\in N_{G}(y)$. Since $|N_{G^{1}}(y)|\geq 3$, let
$v_{1}\in V(G^{1})$ be a neighbor of $y$ such that $v_{1}$ is not an end
vertex of $e$. Let $v_{2k}\in V(G^{2})$ be a vertex adjacent to $y$. Then
$yv_{1}v_{2}\ldots v_{2k}$ and $xu_{1}u_{2}\ldots u_{2k}$ are two copies of
$C_{2k+1}$ in $G^{\prime}$; see the blue and red cycles in Figure 4,
respectively. Observe that the above two cycles, together with the matching
$\\{xy,u_{1}v_{1},u_{2}v_{2},\ldots,u_{2k}v_{2k}\\}$, form a copy of
$C_{2k+1}\square P_{2}$. Thus, we get $C_{2k+1}\square P_{2}\subseteq
G^{\prime}$, as required.

(b) We may assume that $e_{1}\in E(G^{1})$ and $e_{2}\in E(G^{2})$. Similar
with the case (a), one can find a red cycle $C_{2k+1}$ containing the edge
$e_{1}$, and a blue cycle containing $e_{2}$. Indeed, the odd prism
$C_{2k+1}\square P_{2}$ is contained in $K_{2k+1,2k+1}+\\{e_{1},e_{2}\\}$.
Combining with $(K_{2k+1,2k+1}+\\{e_{1},e_{2}\\})\subseteq G$, we then obtain
a copy of $C_{2k+1}\square P_{2}$ in $G$. The proof is completed. ∎

The following well-known lemma proved by Erdős [13] and Simonovits [38] is a
powerful tool in extremal graph problems; see, e.g., Corollary 4.3 in Chapter
6 of [3].

######  Lemma 13 (Erdős [13] and Simonovits [38]).

Let $H$ be a graph with $\chi(H)=p+1\geq 3$. If $G$ is an extremal graph for
$H$ on $n$ vertices, then $\delta(G)=(1-\frac{1}{p})n+o(n)$.

Now, we are ready to give a proof of Theorem 1.

###### Proof of Theorem 1.

Let $G$ be a $C_{2k+1}\square P_{2}$-free graph on $n$ vertices with maximum
number of edges. Our goal is to prove that $G$ is obtained from a complete
bipartite graph $K_{n_{a},n_{b}}$ (where $n_{a}+n_{b}=n$) by embedding an
$n_{a}$-vertex extremal graph for $P_{4}$ into the part of size $n_{a}$. First
of all, it follows from Lemmas 9 and 11 that

$\displaystyle e(G)$
$\displaystyle\geq\max\left\\{n_{a}n_{b}+\mbox{ex}(n_{a},P_{4}):n_{a}+n_{b}=n\right\\}.$
(3)

A simple calculation shows that

$e(G)\geq e(T_{2}(n))+\frac{n}{2}+O(1).$

Now, we are going to apply Theorem 10. After deleting at most $r$ vertices of
$G$, the resulting graph $G^{\prime}$ can be written as the product
$G^{\prime}=G^{1}\otimes G^{2}$ with $n/2-r\leq|V(G^{i})|\leq n/2+r$ for each
$i\in\\{1,2\\}$. Moreover, each component of $G^{i}$ is on at most $r$
vertices. We denote by $D$ the set of deleted vertices. Then $|D|\leq r$. By
Lemma 12 (b), it is impossible that both $G^{1}$ and $G^{2}$ contain an edge.
Then we may assume $G^{2}$ is an independent set of size $n/2+o(n)$. By
Theorem 10, for each $i=1,2$, the isolated vertices of $G^{i}$ are symmetric
subgraphs of $G$. Thus, for any vertex $z\in D$, by the symmetry in Theorem
10, the isolated vertices of $G^{i}$ either all are adjacent to $z$, or all
are not adjacent to $z$.

We divide $D$ into the following two sets: if $x\in D$ is not joint to
vertices of $G^{2}$, then let it belongs to $D_{2}$, otherwise, let it belongs
to $D_{1}$. Let $A_{i}=V(G^{i})\cup D_{i}$ and denote $|A_{i}|=n_{i}$ for
$i=1,2$. Clearly, we have $V(G)=A_{1}\cup A_{2}$. By the symmetry of Theorem
10, each vertex of $A_{1}$ is joint to all vertices of $G^{2}$. By Lemma 13,
we get $\delta(G)\geq n/2+o(n)$. Note that $G^{2}$ is an empty graph and
$|D_{2}|\leq r$. Consequently, each vertex of $G^{2}$ is adjacent to
$n/2+o(n)$ vertices of $A_{1}$. Moreover, each vertex of $D_{2}$ is adjacent
to $n/2-o(n)$ vertices of $G^{1}$.

######  Claim 1.

$G[A_{i}]$ does not contain a copy of $P_{4}$ for each $i\in\\{1,2\\}$.

###### Proof of Claim 1.

From the above discussion, we know that $G[A_{1},V(G^{2})]$ is a complete
bipartite graph. By Definition 8 and Lemma 11, we have $G[A_{1}]$ is
$P_{4}$-free.

Assume on the contrary that $G[A_{2}]$ contains a copy of $P_{4}$. Since
$A_{2}=V(G^{2})\cup D_{2}$ and $E(G^{2})$ is empty, the above copy of $P_{4}$
must be contained in $G[D_{2}]$. Choosing a set $U$ consisting of $4k$
vertices of $A_{2}\backslash V(P_{4})$ arbitrarily, by Lemma 13, we know that
these $4k$ vertices and the vertices of $V(P_{4})$ have at least $n/2-o(n)$
common neighbors in $G^{1}$. By Definition 8 and Lemma 11, there is a copy of
$C_{2k+1}\square P_{2}$ in the subgraph of $G$ induced by the set $U\cup
V(P_{4})$ together with its common neighborhood, and so $G$ contains a copy of
$C_{2k+1}\square P_{2}$, a contradiction. The proof is completed. ∎

Since $|D|\leq r$, by (3), we have
$e(G[A_{1}])\geq\mbox{ex}(|A_{1}|,P_{4})-O(1)$. Thus, by Lemma 7, $G[A_{1}]$
contains a copy of either $K_{1,\ell}$ or $\ell K_{3}$, where
$\ell=\Theta(n)$.

Next, we divide the proof into two cases. For convenience, we write
$N(U):=\cap_{u\in U}N(u)$ for the common neighborhood of vertices of a set $U$
and denote $N_{A}(U):=N(U)\cap A$.

Case 1. $G[A_{1}]$ contains a copy of $\ell K_{3}$. We claim that $A_{2}$ is
an independent set in $G$. Assume on the contrary that $G[A_{2}]$ contains an
edge $xy$. Then $xy$ is contained in $G[D_{2}]$ since $V(G^{2})$ is an
independent set. Let $U_{2}$ be a vertex set consisting of $x,y$ and any
$2k-1$ vertices of $A_{2}\backslash\\{x,y\\}$. By Lemma 13, these $2k+1$
vertices of $U_{2}$ have at least $|A_{1}|-o(n)$ common neighbors in $A_{1}$.
In other words, there are $o(n)$ vertices of $A_{1}$ which are outside of
$N_{A_{1}}(U_{2})$. Since $G[A_{1}]$ has $\ell$ disjoint copies of $K_{3}$ and
$\ell=\Theta(n)$, we obtain that there exists a triangle located in
$N_{A_{1}}(U_{2})$. Consequently, we can choose a set $U_{1}$ consisting of
$2k+1$ vertices in $N_{A_{1}}(U_{2})$ such that $G[U_{1}]$ contain a copy of
$K_{3}$. Note that $G[U_{1}]$ contains an edge and $G[U_{2},U_{1}]$ forms a
complete bipartite subgraph. By Lemma 12 (b), we obtain that $G$ contains a
copy of $C_{2k+1}\square P_{2}$, a contradiction. Thus, there is no edge in
$G[A_{2}]$. Denote $|A_{1}|=n_{1}$ and $|A_{2}|=n_{2}$. Therefore, it follows
from Claim 1 that

$e(G)=n_{1}n_{2}+e(A_{1})\leq\max\left\\{n_{a}n_{b}+\mbox{ex}(n_{a},P_{4}):n_{a}+n_{b}=n\right\\}.$

Combining with (3), we obtain the desired bound on $e(G)$. Moreover, the
extremal graphs for the prism $C_{2k+1}\square P_{2}$ are obtained from a
complete bipartite graph $K_{n_{a},n_{b}}$ by embedding an $n_{a}$-vertex
extremal graph for $P_{4}$ in the part of size $n_{a}$. Furthermore, the
extremal graphs for $P_{4}$ are also characterized by applying Corollary 6.

Case 2. $G[A_{1}]$ contains a copy of $K_{1,\ell}$. Let $u$ be the central
vertex of $K_{1,\ell}$. Then $u$ has at least $\ell=\Theta(n)$ neighbors in
$A_{1}$. Recall that each vertex of $A_{1}$ is joint to all vertices of
$G^{2}$. We denote $\ell_{i}=|N_{A_{i}}(u)|$ for each $i\in\\{1,2\\}$. Then
$\ell_{i}=\Theta(n)$.

######  Claim 2.

There is no edge in $G[A_{1}\setminus\\{u\\}]$ incident with a vertex of
$N_{A_{1}}(u)$. Correspondingly, there is no edge in $G[A_{2}]$ incident with
a vertex of $N_{A_{2}}(u)$

###### Proof.

If there is an edge in $G[A_{1}\setminus\\{u\\}]$ incident with a vertex of
$N_{A_{1}}(u)$, then $G[A_{1}]$ contains a copy of $P_{4}$, which contradicts
with Claim 1. Hence there is no edge in $G[A_{1}\setminus\\{u\\}]$ incident
with a vertex of $N_{A_{1}}(u)$. If there is an edge $xy$ in $G[A_{2}]$
incident with a vertex of $N_{A_{2}}(u)$, then $x,y\in D_{2}$ since $G^{2}$
has no edge. Let $E_{2}$ be a vertex set consisting of $x,y$ and any $2k$
vertices of $N_{G^{2}}(u)$. It follows that these $2k+2$ vertices of $E_{2}$
have $|A_{1}|-o(n)$ common neighbors in $A_{1}$. Since $u$ has
$\ell_{1}=\Theta(n)$ neighbors in $A_{1}$, we know that

$|N_{A_{1}}(E_{2})\cap
N_{A_{1}}(u)|\geq|N_{A_{1}}(E_{2})|+|N_{A_{1}}(u)|-|A_{1}|\geq\ell_{1}-o(n)\geq
2k+1.$

Thus, we can choose a set $E_{1}$ consisting of $2k+1$ vertices of
$N_{A_{1}}(E_{2})\cap N_{A_{1}}(u)$. Note that
$|N_{E_{1}}(u)|=2k+1,|N_{E_{2}}(u)|\geq 2k+1$ and $G[E_{1},E_{2}]$ is a
complete bipartite graph. By Lemma 12 (a), the sets $E_{1}$, $E_{2}$, and the
vertex $u$, induce a graph containing a copy of $C_{2k+1}\square P_{2}$. This
is a contradiction. Thus there is no edge in $G[A_{2}]$ incident with a vertex
of $N_{A_{2}}(u)$. ∎

We write $e(A)$ for the number of edges of $G[A]$. From Claim 2, we obtain

$\displaystyle e(A_{1})$
$\displaystyle=e(N_{A_{1}}(u)\cup\\{u\\})+e(A_{1}\setminus(N_{A_{1}}(u)\cup\\{u\\}))$
$\displaystyle\leq\ell_{1}+\mbox{ex}(n_{1}-1-\ell_{1},P_{4})\leq\ell_{1}+(n_{1}-1-\ell_{1})\leq\mbox{ex}(n_{1},P_{4}),$
(4)

where the first inequality holds by Claim 1, and the others hold by Corollary
6. Applying Claim 2, we obtain that $N_{A_{2}}(u)$ is an independent set in
$G[A_{2}]$. Thus, we get

$\displaystyle e(A_{2})=e(A_{2}\setminus
N_{A_{2}}(u))\leq\mbox{ex}(n_{2}-\ell_{2},P_{4})\leq n_{2}-\ell_{2}.$ (5)

Since $u$ has $n_{2}-\ell_{2}$ non-neighbors in $A_{2}$, we obtain that

$e(A_{1},A_{2})\leq n_{1}n_{2}-(n_{2}-\ell_{2}).$ (6)

Note that $e(G)=e(A_{1},A_{2})+e(A_{1})+e(A_{2})$. Combining (4), (5) and (6),
we have

$\displaystyle e(G)\leq
n_{1}n_{2}+\mbox{ex}(n_{1},P_{4})\leq\max\left\\{n_{a}n_{b}+\mbox{ex}(n_{a},P_{4}):n_{a}+n_{b}=n\right\\}.$
(7)

Hence, by (3), we have
$e(G)=\max\left\\{\mbox{ex}(n_{a},P_{4})+n_{a}n_{b}:n_{a}+n_{b}=n\right\\}$.

Furthermore, using Corollary 6, we obtain

$e(G)=\max\limits_{n_{a}+n_{b}=n}\left\\{n_{a}(1+n_{b})+\frac{1}{2}(j^{2}-3j):j\in\\{0,1,2\\},j\equiv
n_{a}(\mathrm{mod}~{}3)\right\\}.$

Finally, we will characterize the extremal graphs. If the equality holds in
(7), then from the above proof, we must have equalities in (4), (5) and (6).
Denote $t_{1}:=n_{1}-1-\ell_{1}$ and $t_{2}:=n_{2}-\ell_{2}$. Then for
$i=1,2$, we have

$\displaystyle\operatorname{ex}(t_{i},P_{4})=t_{i}.$ (8)

Moreover, attaining equality in (6) yields that each vertex of
$A_{1}\backslash\\{u\\}$ is adjacent to each vertex of $A_{2}$. By Corollary
6, if $t_{i}>0$, then $t_{i}\equiv 0~{}(\bmod~{}3)$, and so $t_{i}\geq 3$. In
addition, Corollary 6 also implies that an extremal graph for $P_{4}$ on at
least 3 vertices contains a copy of $P_{3}$. If both $t_{1}$ and $t_{2}$ are
not zero, then by (8), both $G[A_{1}\backslash\\{u\\}]$ and $G[A_{2}]$ contain
a copy of $P_{2}$. Hence by Lemma 12 (b), $G$ contains a copy of
$C_{2k+1}\square P_{2}$, a contradiction. Thus, at most one of $t_{1}$ and
$t_{2}$ is not zero. Firstly, if $t_{1}\neq 0$ and $t_{2}=0$, then
$A_{2}=N_{A_{2}}(u)$ and $A_{2}$ is an independent set in $G$. Recall in Claim
1 that $G[A_{1}]$ is $P_{4}$-free. Then $G$ is obtained from $K_{n_{1},n_{2}}$
by embedding an extremal graph for $P_{4}$ into the part $A_{1}$. Secondly, if
$t_{1}=0$ and $t_{2}\neq 0$, then $u$ is adjacent to all vertices of
$A_{1}\setminus\\{u\\}$. Moving the vertex $u$ to the set $A_{2}$, and we
denote $B_{1}:=A_{1}\backslash\\{u\\}$ and $B_{2}:=A_{2}\cup\\{u\\}$. Recall
in Claim 2 that there is no edge in $G[A_{1}\setminus\\{u\\}]$ incident with a
vertex of $N_{A_{1}}(u)=A_{1}\setminus\\{u\\}$, so $B_{1}$ is an independent
set. Moreover, $G[B_{1},B_{2}]$ is a complete bipartite graph and $G[B_{2}]$
is $P_{4}$-free, as desired. Finally, if $t_{1}=t_{2}=0$, then
$G[A_{1},A_{2}]$ is a complete bipartite graph, $G[A_{1}]$ is a star
$K_{1,n_{1}-1}$, and $G[A_{2}]$ is an empty graph, as required. To sum up,
every extremal graph for $C_{2k+1}\square P_{2}$ is the join of an
$n_{a}$-vertex extremal graph for $P_{4}$ and an $n_{b}$-vertex independent
set. ∎

##  4 Some Lemmas for the triangular prism

In this section, we shall consider the triangular prism in Figure 2. In the
case $k=1$ of Theorem 1, we will throw away the condition that requires the
order $n$ being sufficiently large. Using a quite different method, we will
determine all $n$-vertex extremal graphs of the prism $C_{3}\square P_{2}$ for
every integer $n\geq 6$. To begin with, we need to present some lemmas.

###  4.1 A result for the power of a path

The $p$-th power of a path $P_{k}$ on $k$ vertices, denoted by $P_{k}^{p}$, is
the graph obtained from $P_{k}$ by joining each pair of vertices of $P_{k}$
with distance at most $p$; see Figure 5.

$v_{1}$$v_{2}$$v_{3}$$v_{4}$$v_{5}$$v_{6}$$v_{1}$$v_{2}$$v_{3}$$v_{4}$$v_{5}$$v_{6}$
Figure 5: The triangular prism $C_{3}\square P_{2}$ and the graph $P_{6}^{2}$,
respectively

In order to study $\operatorname{ex}(n,C_{3}\square P_{2})$, we need to use a
result from Xiao, Katona, Xiao and Zamora [45] in which they determined the
exact value of $\operatorname{ex}(n,P_{5}^{2})$ and
$\operatorname{ex}(n,P_{6}^{2})$, respectively. For the power of a long path,
see Yuan [51] for more results. In addition, the Turán number
$\mathrm{ex}(n,P_{4}^{2})$ can be deduced from a general result of Dirac [10],
which states that if $r\geq 3,n\geq r+1$ and $G$ is an $n$-vertex graph with
more than $e(T_{r-1}(n))$ edges, then $G$ contains a copy of $K_{r+1}^{-}$,
where $K_{r+1}^{-}$ is the graph obtained from $K_{r+1}$ by deleting any one
edge. Setting $r=3$ and observing that $P_{4}^{2}=K_{4}^{-}$, we obtain
$\mathrm{ex}(n,P_{4}^{2})=\lfloor n^{2}/4\rfloor$ for each integer $n\geq 4$.

Before showing the proofs of Theorems 2 and 3, we need the following results.

######  Theorem 14 (Xiao et al. [45]).

The maximum number of edges in an $n$-vertex $P^{2}_{6}$-free graph $(n\neq
5)$ is

$\operatorname{ex}(n,P^{2}_{6})=\begin{cases}\left\lfloor\frac{n^{2}}{4}\right\rfloor+\left\lfloor\frac{n-1}{2}\right\rfloor,&\text{if}~{}n\equiv
1,2,3~{}(\bmod~{}6),\\\\[5.69054pt]
\left\lfloor\frac{n^{2}}{4}\right\rfloor+\left\lceil\frac{n}{2}\right\rceil,&\text{otherwise.}\end{cases}$

######  Theorem 15 (Xiao et al. [45]).

Let $n\geq 6$ be a natural number. The extremal graphs for $P_{6}^{2}$ are the
following ones.

When $n\equiv 1\pmod{6}$ then $F_{n}^{\lceil{\frac{n}{2}}\rceil,j}$ and
$H_{n}^{\lfloor{\frac{n}{2}}\rfloor}$;

when $n\equiv 2\pmod{6}$ then $F_{n}^{{\frac{n}{2}},j}$ and
$F_{n}^{{\frac{n}{2}}+1,j}$;

when $n\equiv 3\pmod{6}$ then $F_{n}^{\lceil{\frac{n}{2}}\rceil,j}$ and
$H_{n}^{\lceil{\frac{n}{2}}\rceil+1}$;

when $n\equiv 0,4,5\pmod{6}$ then $H_{n}^{{\frac{n}{2}}}$,
$H_{n}^{{\frac{n}{2}}+1}$ and $H_{n}^{\lceil{\frac{n}{2}}\rceil}$,
respectively, where $j$ can have all the values satisfying the conditions
$j\leq i$ and $3\mid(i-j)$.

Comparing the above theorems with Theorems 2 and 3, it is surprising that the
Turán numbers of graphs $C_{3}\square P_{2}$ and $P_{6}^{2}$ are completely
the same, although their structures are different. In addition, it is
noteworthy that the extremal graphs for $C_{3}\square P_{2}$ and $P_{6}^{2}$
are also the same except for three small graphs $G_{1},G_{2}$ and $G_{3}$,
depicted in Figure 3.

In fact, it is a key relation between $C_{3}\square P_{2}$ and $P_{6}^{2}$
that $\mathcal{M}(C_{3}\square P_{2})=\mathcal{M}(P_{6}^{2})=\\{P_{4}\\}$,
where $\mathcal{M}(L)$ is the decomposition family of $L$ stated in Definition
8. To a certain extent, the above phenomenon reveals that the decomposition
family of a graph could determine the Turán number of a graph and also
dominate the structures of the extremal graphs.

###  4.2 The $C_{3}\square P_{2}$-free graphs containing $P_{6}^{2}$ as a
subgraph

Before showing the proof of Theorems 2 and 3, we next present some useful
lemmas for a special class of $C_{3}\square P_{2}$-free graphs which contain
the $2$-power graph $P_{6}^{2}$ as a subgraph.

######  Lemma 16.

Let $G$ be a $C_{3}\square P_{2}$-free graph on $6$ vertices. If $G$ contains
a copy of $P_{6}^{2}$, then $e(G)\leq 12$, with equality holding if and only
if $G=G_{1}$.

$v_{1}$$v_{2}$$v_{3}$$v_{4}$$v_{6}$$v_{5}$$v_{1}$$v_{2}$$v_{3}$$v_{4}$$v_{5}$$v_{6}$
Figure 6: Two drawings of the graph $G_{1}$

###### Proof.

The proof is a standard argument on case-analysis. Since $G$ has $6$ vertices
and $P_{6}^{2}$ is contained in $G$, we may assume that
$V(G)=\\{v_{1},v_{2},\ldots,v_{6}\\}$, where
$v_{1}v_{3},v_{2}v_{4},v_{3}v_{5}$ and $v_{4}v_{6}$ are edges of $G$. Clearly,
we have $9\leq e(G)\leq 15$. To prove $e(G)\leq 12$, it is equivalent to show
that there missed at least three edges in $G$ whenever $G$ is $C_{3}\square
P_{2}$-free.

First of all, we claim that $v_{1}v_{6}$ can not be an edge of $G$. Otherwise,
if $v_{1}v_{6}\in E(G)$, then two triangles $v_{1}v_{2}v_{3}$ and
$v_{6}v_{4}v_{5}$, together with three edges
$v_{1}v_{6},v_{2}v_{4},v_{3}v_{5}$ form a copy of $C_{3}\square P_{2}$, a
contradiction. Thus, we get $2\leq d_{G}(v_{1})\leq 4$.

Case 1. $d_{G}(v_{1})=2$. More precisely, we have
$v_{1}v_{4},v_{1}v_{5},v_{1}v_{6}\notin E(G)$, and $G$ misses at least three
edges of $K_{6}$. Clearly, we have $e(G)\leq 12$. If $e(G)=12$, then
$v_{2}v_{5},v_{2}v_{6}$ and $v_{3}v_{6}$ are edges of $G$. In this case, we
get $G=G_{1}$, as required.

Case 2. $d_{G}(v_{1})=3$. In other words, we have either $v_{1}v_{4}\in E(G)$
or $v_{1}v_{5}\in E(G)$. In the former case, if $v_{1}v_{4}\in E(G)$, then
$v_{2}v_{6}\notin E(G)$. Otherwise, if $v_{2}v_{6}\in E(G)$, then two
triangles $v_{1}v_{2}v_{3}$ and $v_{4}v_{6}v_{5}$, together with edges
$v_{1}v_{4},v_{2}v_{6},v_{3}v_{5}$ form a copy of $C_{3}\square P_{2}$, a
contradiction. Hence, we conclude that $v_{1}v_{6},v_{1}v_{5}$ and
$v_{2}v_{6}$ are not edges of $G$, which leads to $e(G)\leq 12$. If $e(G)=12$,
then $v_{1}v_{4},v_{2}v_{5},v_{3}v_{6}$ are edges of $G$, which together with
two triangles $v_{1}v_{2}v_{3}$ and $v_{4}v_{5}v_{6}$ form a copy of
$C_{3}\square P_{2}$, a contradiction. Hence $e(G)\leq 11$.

In the later case, that is, $v_{1}v_{5}\in E(G)$ and
$v_{1}v_{4},v_{1}v_{6}\notin E(G)$. Furthermore, we can get $v_{2}v_{6}\notin
E(G)$ and $v_{3}v_{6}\notin E(G)$. Otherwise, if $v_{2}v_{6}\in E(G)$, then
triangles $v_{1}v_{2}v_{3}$ and $v_{5}v_{6}v_{4}$, with edges
$v_{1}v_{5},v_{2}v_{6},v_{3}v_{4}$ form a copy of $C_{3}\square P_{2}$, a
contradiction. If $v_{3}v_{6}\in E(G)$, then triangles $v_{1}v_{2}v_{3}$ and
$v_{5}v_{4}v_{6}$, with edges $v_{1}v_{5},v_{2}v_{4},v_{3}v_{6}$ form a copy
of $C_{3}\square P_{2}$, a contradiction. Therefore, we have $e(G)\leq 11$.

Case 3. $d_{G}(v_{1})=4$. In this case, we have $v_{1}v_{4},v_{1}v_{5}\in
E(G)$. Similar with the later case of Case 2, we get $v_{2}v_{6}\notin E(G)$
and $v_{3}v_{6}\notin E(G)$ as well. Recall that $v_{1}v_{6}\notin E(G)$.
Consequently, we obtain $e(G)\leq 12$. If $e(G)=12$, then $v_{2}v_{5}\in
E(G)$. By reversing the order of $v_{1}v_{2}\cdots v_{6}$, it is not hard to
see that $G$ is isomorphic to $G_{1}$, as required. ∎

In the following, we always assume that

$P^{2}_{6}\subseteq G.$ (9)

It can be checked that each vertex $v\in V(G)\setminus V(P_{6}^{2})$ can be
adjacent to at most 4 vertices of the copy of $P_{6}^{2}$. Otherwise, if there
is a vertex with $5$ neighbors in $P_{6}^{2}$, then we can find a copy of
$C_{3}\square P_{2}$ in $G$, a contradiction. Assume that the subgraph
$P_{6}^{2}$ is obtained from $P_{6}=v_{1}v_{2}\cdots v_{6}$ by joining each
pair of vertices of $V(P_{6})$ with distance at most 2.

The following claim holds immediately under the condition (9).

######  Claim 3.

If $v\in V(G)\setminus V(P_{6}^{2})$ is adjacent to exactly 4 vertices of
$P_{6}^{2}$, then there are exactly 4 adjacency relations (up to graph
isomorphism) between $v$ and $P_{6}^{2}$; see Figure 7.

Type 1Type 2Type 3Type
4$v_{1}$$v_{2}$$v_{3}$$v_{4}$$v_{5}$$v_{6}$$v$$v_{1}$$v_{2}$$v_{3}$$v_{4}$$v_{5}$$v_{6}$$v$$v$$v_{1}$$v_{2}$$v_{3}$$v_{4}$$v_{5}$$v_{6}$$v$$v$$v_{1}$$v_{2}$$v_{3}$$v_{4}$$v_{5}$$v_{6}$$v$$v$
Figure 7: Four types for the vertex $v$ satisfying $|N(v)\cap V(P^{2}_{6})|=4$

Furthermore, the following lemma can be verified case by case.

######  Lemma 17.

There are at most $2$ vertices of $V(G)\setminus V(P^{2}_{6})$ adjacent to
exactly $4$ vertices of $V(P^{2}_{6})$. Moreover, if $x,y\in V(G)\setminus
V(P_{6}^{2})$ are such two vertices, then there are only $2$ adjacency
relations between $\\{x,y\\}$ and $P_{6}^{2}$, and moreover $xy\notin E(G)$;
see Figure 8.

$v_{1}$$v_{2}$$v_{3}$$v_{4}$$v_{5}$$v_{6}$$x$$x$$y$$y$$H_{1}$$v_{1}$$v_{2}$$v_{3}$$v_{4}$$v_{5}$$v_{6}$$x$$x$$y$$y$$H_{2}$
Figure 8: The $8$-vertex graphs $H_{1}$ and $H_{2}$, respectively.

###### Proof.

First of all, we show that if $x,y$ are two vertices in the same type, then
$G$ contains a copy of $C_{3}\square P_{2}$, except that they are of Type 1,
drawing as $H_{2}$ in Figure 8. Indeed, if $x,y$ are of Type 1, then either
$N_{P_{6}^{2}}(x)=N_{P_{6}^{2}}(y)=\\{v_{1},v_{2},v_{3},v_{4}\\}$, or
$N_{P_{6}^{2}}(x)=\\{v_{1},v_{2},v_{3},v_{4}\\}$ and
$N_{P_{6}^{2}}(y)=\\{v_{6},v_{5},v_{4},v_{3}\\}$. For the former case, the
triangles $v_{1}v_{3}x$ and $v_{2}v_{4}y$, together with three edges
$v_{1}y,v_{3}v_{4},xv_{2}$, form a copy of $C_{3}\square P_{2}$, a
contradiction; For the latter case, it is possible, and stated as $H_{2}$ in
Figure 8. If $x,y$ are of Type 2, then the symmetry gives
$N_{P_{6}^{2}}(x)=N_{P_{6}^{2}}(y)=\\{v_{2},v_{3},v_{4},v_{5}\\}$. Then the
triangles $v_{2}v_{3}x$ and $v_{4}v_{5}y$, with the edges
$v_{2}y,v_{3}v_{5},xv_{4}$ form a copy of $C_{3}\square P_{2}$. If $x,y$ are
of Type 3, then
$N_{P_{6}^{2}}(x)=N_{P_{6}^{2}}(y)=\\{v_{1},v_{3},v_{4},v_{6}\\}$. Thus, the
triangles $v_{1}v_{3}x$ and $v_{4}v_{6}y$ form a copy of $C_{3}\square P_{2}$
since $v_{1}y,v_{3}v_{4},xv_{6}$ are edges of $G$. If $x,y$ are of Type 4,
then either $N_{P_{6}^{2}}(x)=N_{P_{6}^{2}}(y)=\\{v_{1},v_{3},v_{5},v_{6}\\}$,
or $N_{P_{6}^{2}}(x)=\\{v_{1},v_{3},v_{5},v_{6}\\}$ and
$N_{P_{6}^{2}}(y)=\\{v_{6},v_{4},v_{2},v_{1}\\}$. For the former case, we can
see that triangles $v_{1}v_{3}x$ and $v_{5}v_{6}y$ form a copy of
$C_{3}\square P_{2}$ since $v_{1}y,xv_{6},v_{3}v_{5}$ are edges in $G$. For
the latter case, it can be seen that $G$ contains a copy of $C_{3}\square
P_{2}$ as witnessed by triangles $v_{1}v_{3}x$ and $v_{6}v_{4}y$ with three
edges $v_{1}y,xv_{6}$ and $v_{3}v_{4}$.

Secondly, one consider the case that $x,y$ are vertices with different types.
More precisely, if $x$ is of Type 1 and $y$ is of Type 2, then $G$ has a copy
of $C_{3}\square P_{2}$ consisting of the triangles $xv_{1}v_{2},yv_{3}v_{4}$
and the edges $v_{1}v_{3},v_{2}y,xv_{4}$. If $x$ is of Type 1 and $y$ is of
Type 3, then the triangles $xv_{1}v_{2},yv_{3}v_{4}$ and the edges
$v_{1}y,v_{2}v_{3},xv_{4}$ form a copy of $C_{3}\square P_{2}$ in $G$. If $x$
is of Type 1 and $y$ is of Type 4, then by symmetry, we get either
$N_{P_{6}^{2}}(x)=\\{v_{1},v_{2},v_{3},v_{4}\\}$ and
$N_{P_{6}^{2}}(y)=\\{v_{1},v_{3},v_{5},v_{6}\\}$, or
$N_{P_{6}^{2}}(x)=\\{v_{6},v_{5},v_{4},v_{3}\\}$ and
$N_{P_{6}^{2}}(y)=\\{v_{1},v_{3},v_{5},v_{6}\\}$. To avoid a copy of
$C_{3}\square P_{2}$ in $G$, the former case is possible, which are stated as
$H_{1}$ in Figure 8. For the latter case, one can find a copy of $C_{3}\square
P_{2}$ on the triangles $xv_{4}v_{6},yv_{3}v_{5}$ with the edges
$xv_{3},v_{4}v_{5},v_{6}y$. If $x$ is of Type 2 and $y$ is of Type 3, then $G$
contains a copy of $C_{3}\square P_{2}$, which appears on the triangles
$xv_{2}v_{4},yv_{1}v_{3}$ and the edges $xv_{3},v_{2}v_{1},v_{4}y$. If $x$ is
of Type 2 and $y$ is of Type 4, then $G$ has a copy of $C_{3}\square P_{2}$ by
combining the triangles $xv_{3}v_{4},yv_{5}v_{6}$ with the edges
$v_{3}y,v_{4}v_{6},xv_{5}$. If $x$ is of Type 3 and $y$ is of Type 4, then one
can find a copy of $C_{3}\square P_{2}$ on the triangles
$xv_{1}v_{3},yv_{5}v_{6}$ with the edges $xv_{6},v_{1}y,v_{3}v_{5}$.

Moreover, it can be checked further that $V(G)\setminus V(P_{6}^{2})$ does not
contain three vertices which are adjacent to $4$ vertices of $P_{6}^{2}$.
Otherwise, if such three vertices exist, i.e., we add one more vertex with
degree $4$ on $P_{6}^{2}$ to the graph $H_{1}$ or $H_{2}$, then one can check
that there is a copy of $C_{3}\square P_{2}$ in $G$. Finally, if $xy$ is an
edge of $G$, then either $H_{1}+xy$ or $H_{2}+xy$ can have a copy of
$C_{3}\square P_{2}$. Indeed, in both cases, the copy will appear on the
triangles $v_{2}v_{4}x$ and $v_{3}v_{5}y$, with the edges
$v_{2}v_{3},v_{4}v_{5},xy$. Thus, we get $xy\notin E(G)$. ∎

######  Lemma 18.

If $G$ contains $H_{1}$ as a subgraph, then $e(G[V(P^{2}_{6})])\leq 10$,
equality holds if and only if $v_{3}v_{6}$ is an edge in $G$.

###### Proof.

Observe that $e(P_{6}^{2})=9$. In other words, we need to show that one can
join at most one non-edge of $P_{6}^{2}$ to avoid the copy of $C_{3}\square
P_{2}$ in $G$. Note that

$E(K_{6})\setminus
E(P_{6}^{2})=\\{v_{1}v_{4},v_{1}v_{5},v_{1}v_{6},v_{2}v_{5},v_{2}v_{6},v_{3}v_{6}\\}.$
(10)

If $v_{1}v_{4}\in E(G[V(P^{2}_{6})])$, then $G$ contains two triangles
$v_{1}v_{4}x$ and $v_{3}v_{5}y$, which together with the matching
$\\{v_{1}y,v_{4}v_{5},xv_{3}\\}$, form a copy of $C_{3}\square P_{2}$, a
contradiction. If $v_{1}v_{5}\in E(G[V(P^{2}_{6})])$, then the triangles
$v_{1}v_{2}x$ and $v_{3}v_{4}v_{5}$, with the matching
$\\{v_{1}v_{5},v_{2}v_{3},xv_{4}\\}$, form a copy of $C_{3}\square P_{2}$, a
contradiction. If $v_{1}v_{6}\in E(G[V(P^{2}_{6})])$, then there are two
triangles $v_{1}v_{3}x$ and $v_{4}v_{5}v_{6}$, combining with the matching
$\\{v_{1}v_{6},v_{3}v_{5},xv_{4}\\}$, we find a copy of $C_{3}\square P_{2}$,
a contradiction. In fact, whenever $v_{1}v_{6}\in E(G)$, one can find a copy
of $C_{3}\square P_{2}$ without the use of the vertex $x$, which was showed in
the second paragraph of the proof of Lemma 16. If $v_{2}v_{5}\in
E(G[V(P^{2}_{6})])$, then triangles $v_{1}v_{2}x$ and $v_{3}v_{4}v_{5}$, with
the matching $\\{v_{1}v_{3},v_{2}v_{5},xv_{4}\\}$, form a copy of
$C_{3}\square P_{2}$, a contradiction. If $v_{2}v_{6}\in E(G[V(P^{2}_{6})])$,
then $G$ contains a copy of $C_{3}\square P_{2}$, which consists of two
triangles $v_{2}v_{3}x$ and $v_{4}v_{5}v_{6}$, with the matching
$\\{v_{2}v_{6},v_{3}v_{5},xv_{4}\\}$. Thus, the only possible case is
$v_{3}v_{6}\in E(G[V(P^{2}_{6})])$, and then it follows that
$e(G[V(P^{2}_{6})])\leq 10$. ∎

Similarly, we can prove the following lemma.

######  Lemma 19.

If $G$ contains $H_{2}$ as a subgraph, then $e(G[V(P^{2}_{6})])\leq 11$,
equality holds if and only if both $v_{1}v_{4}$ and $v_{3}v_{6}$ are edges in
$G$.

###### Proof.

We need to check each non-edge of $E(P_{6}^{2})$ stated in (10). If
$v_{1}v_{5}\in E(G[V(P^{2}_{6})])$, then the triangles $v_{1}v_{2}x$ and
$v_{3}v_{4}v_{5}$, with the matching $\\{v_{1}v_{5},v_{2}v_{4},xv_{3}\\}$,
form a copy of $C_{3}\square P_{2}$, a contradiction. If $v_{1}v_{6}\in
E(G[V(P^{2}_{6})])$, then the same argument in the proof of Lemma 18 can yield
a copy of $C_{3}\square P_{2}$, a contradiction. In addition, combining the
triangles $v_{1}v_{3}x,v_{4}v_{6}y$ with the matching
$\\{v_{1}v_{6},v_{3}y,xv_{4}\\}$, we find another copy of $C_{3}\square
P_{2}$. If $v_{2}v_{5}\in E(G[V(P^{2}_{6})])$, then the proof of Lemma 18
yields a copy of $C_{3}\square P_{2}$, a contradiction. Additionally, there is
another copy of $C_{3}\square P_{2}$ on two triangles $v_{2}v_{3}x$ and
$v_{4}v_{5}y$, joined by the matching $\\{v_{2}v_{5},v_{3}y,xv_{4}\\}$.
Finally, if $v_{2}v_{6}\in E(G[V(P^{2}_{6})])$, then there is a copy of
$C_{3}\square P_{2}$ in $G$, which consists of triangles
$v_{2}v_{3}x,v_{4}v_{6}y$ and the matching $\\{v_{2}v_{6},v_{3}y,xv_{4}\\}$.
Therefore, it is possible that $v_{1}v_{4},v_{3}v_{6}\in E(G[V(P^{2}_{6})])$,
and only in such a case, we have $e(G[V(P^{2}_{6})])=11$. ∎

##  5 Proofs of Theorems 2 and 3

In this section, we shall prove Theorems 2 and 3 as follows.

###### Proof of Theorem 2.

For notational convenience, we denote

$f_{C_{3}\square
P_{2}}(n):=\begin{cases}\left\lfloor\frac{n^{2}}{4}\right\rfloor+\left\lfloor\frac{n-1}{2}\right\rfloor,&~{}\text{if}~{}n\equiv
1,2,3~{}(\bmod~{}6),\\\\[8.53581pt]
\left\lfloor\frac{n^{2}}{4}\right\rfloor+\left\lceil\frac{n}{2}\right\rceil,&~{}\text{otherwise}.\end{cases}$

First of all, when $n\equiv 0,4,5~{}(\bmod~{}6)$, we have
$\operatorname{ex}(n,C_{3}\square
P_{2})\geq\lfloor\frac{n^{2}}{4}\rfloor+\lceil\frac{n}{2}\rceil$, which
follows from the constructions of $G_{1}$, $H^{\frac{n}{2}}_{n}$,
$H^{\frac{n}{2}+1}_{n}$ and $H^{\lceil\frac{n}{2}\rceil}_{n}$, respectively.
In addition, when $n\equiv 1,2,3~{}(\bmod~{}6)$, the lower bound
$\operatorname{ex}(n,C_{3}\square
P_{2})\geq\lfloor\frac{n^{2}}{4}\rfloor+\lfloor\frac{n-1}{2}\rfloor$ follows
from the definitions of $G_{2}$, $G_{3}$ and
$F^{\lceil\frac{n}{2}\rceil,j}_{n}$. Thus, it remains to show the following
inequality

$\displaystyle\operatorname{ex}(n,C_{3}\square P_{2})\leq f_{C_{3}\square
P_{2}}(n).$ (11)

Our proof of (11) is by induction on $n$. Let $G$ be an $n$-vertex
$C_{3}\square P_{2}$-free graph, we need to show that $e(G)\leq
f_{C_{3}\square P_{2}}(n)$. Since our inductive step will go from $n-6$ to
$n$, we have to prove the base case in each residue class $\bmod~{}6$.

§ Base Case §

When $1\leq n\leq 4$, it is clear that $K_{n}$ is the $C_{3}\square
P_{2}$-free graph with the maximum number of edges, and one can verify that
$e(K_{n})=f_{C_{3}\square P_{2}}(n)$. Moreover, when $n=6$, by Theorem 14, we
have $e(G)\leq 12$ whenever $G$ is $P_{6}^{2}$-free; by Lemma 16, we get
$e(G)\leq 12$ whenever $G$ has a copy of $P_{6}^{2}$. Anyway, we always have
$e(G)\leq 12=f_{C_{3}\square P_{2}}(6)$, as needed.

We remark here that when $n=5$, we have

$\mathrm{ex}(5,C_{3}\square P_{2})=e(K_{5})=10>9=f_{C_{3}\square P_{2}}(5).$
(12)

This is a counterexample. Thus we require $n\neq 5$.

Next, we are going to prove the statement for $n=11$. First of all, if
$P^{2}_{6}\nsubseteq G$, then by Theorem 14, the results hold immediately. In
what follows, we assume that $P^{2}_{6}\subseteq G$. Under this constraint,
our aim is to show that

$e(G)<f_{C_{3}\square P_{2}}(11)=36.$ (13)

Firstly, if $V(G)\setminus V(P_{6}^{2})$ forms a copy of $K_{5}$ in $G$, then
each $v_{i}\in V(P_{6}^{2})$ is adjacent to at most 2 vertices of $K_{5}$,
otherwise, there is a copy of $C_{3}\square P_{2}$ in $G$. By Lemma 16, we get
$e(G[V(P^{2}_{6})])\leq 12$. Therefore, we have $e(G)\leq
12+12+10=34<36=f_{C_{3}\square P_{2}}(11)$.

Secondly, if $V(G)\setminus V(P_{6}^{2})$ forms a copy of $K_{5}^{-}$ in $G$,
then we assume that $V(K_{5}^{-})=\\{u_{1},u_{2},u_{3},u_{4},u_{5}\\}$ and
$u_{4}u_{5}\notin E(K_{5}^{-})$. The following two facts can be checked. The
first fact asserts that for each $i\in\\{1,\ldots,6\\}$, the vertex $v_{i}$ is
adjacent to at most 3 vertices of $K_{5}^{-}$, with equality holding if and
only if $N_{K_{5}^{-}}(v_{i})=\\{u_{1},u_{2},u_{3}\\}$, otherwise, it leads to
$C_{3}\square P_{2}\subseteq G$. The second fact states that there are at most
$7$ edges between $\\{v_{1},v_{2},v_{3}\\}$ and $V(K_{5}^{-})$, otherwise, one
can get $C_{3}\square P_{2}\subseteq G$. The similar result holds between
$\\{v_{4},v_{5},v_{6}\\}$ and $K_{5}^{-}$. Therefore, the number of edges
between $V(P^{2}_{6})$ and $V(K_{5}^{-})$ is at most $14$. Recall in Lemma 16
that $e(G[V(P^{2}_{6})])\leq 12$. Therefore, we get $e(G)\leq
12+14+9=35<f_{C_{3}\square P_{2}}(11)$.

Finally, we will consider the remaining case

$e(V(G)\setminus V(P^{2}_{6}))\leq 8.$

By Lemma 17, we proceed in the following three possible cases.

Case 1. There are exactly 2 vertices of $V(G)\setminus V(P^{2}_{6})$, say $x$
and $y$, each of them is adjacent to 4 vertices of $V(P^{2}_{6})$. By Lemma
17, we obtain that either $H_{1}\subseteq G$ or $H_{2}\subseteq G$.

Subcase 1.1. If $H_{1}\subseteq G$, then by Lemma 18, we know that
$e(G[V(P^{2}_{6})])\leq 10$. Consequently, we have $e(G)\leq
10+(4+4+3+3+3)+8=35<f_{C_{3}\square P_{2}}(11)$, as desired.

Subcase 1.2. If $H_{2}\subseteq G$, then by Lemma 19, we have
$e(G[V(P^{2}_{6})])\leq 11$, equality holds if and only if both $v_{1}v_{4}$
and $v_{3}v_{6}$ are edges of $G$. If there is a vertex of
$V(G)\setminus(V(P^{2}_{6})\cup\\{x,y\\})$ adjacent to at most 2 vertices of
$V(P^{2}_{6})$, then $e(G)\leq 11+(4+4+2+3+3)+8=35<f_{C_{3}\square
P_{2}}(11)$, as desired. If every vertex of
$V(G)\setminus(V(P^{2}_{6})\cup\\{x,y\\})$ is adjacent to 3 vertices of
$V(P^{2}_{6})$, then it can be seen further that $e(G[V(P^{2}_{6})])\leq 10$.
Otherwise, if $e(G[V(P^{2}_{6})])=11$, then Lemma 19 implies
$v_{1}v_{4},v_{3}v_{6}\in E(G)$. Any vertex of
$V(G)\setminus(V(P^{2}_{6})\cup\\{x,y\\})$ with degree $3$ on $V(P_{6}^{2})$
can lead to a copy of $C_{3}\square P_{2}$, a contradiction. Therefore, we
have $e(G)\leq 10+(4+4+3\times 3)+8=35<f_{C_{3}\square P_{2}}(11)$, as
required.

Case 2. There is exactly one vertex $v\in V(G)\setminus V(P^{2}_{6})$, which
is adjacent to 4 vertices of $V(P^{2}_{6})$. By Claim 3, $v$ is one of the
four types in Figure 7. In either case, by Lemma 16, we can get
$G[V(P^{2}_{6})]\neq G_{1}$ and then $e(G[V(P^{2}_{6})])\leq 11$. Otherwise,
if $G[V(P^{2}_{6})]=G_{1}$, then $v_{2}v_{5},v_{2}v_{6}$ and $v_{3}v_{6}$ are
edges of $G$. Observe that the vertex set $\\{v_{2},v_{3},\ldots,v_{6}\\}$
forms a copy of the complete graph $K_{5}$ in $G$. Since $v$ has $4$ neighbors
on $P_{6}^{2}$, we know that there are at least $3$ neighbors of $v$ which are
contained in the set $\\{v_{2},v_{3},\ldots,v_{6}\\}$. A trivial fact states
that if $v$ has at least $3$ neighbors on $K_{5}$, then $\\{v\\}\cup V(K_{5})$
contains a copy of $C_{3}\square P_{2}$. Thus $G$ has a copy of $C_{3}\square
P_{2}$. Therefore, we have $e(G)\leq 11+(4+3\times 4)+8=35<f_{C_{3}\square
P_{2}}(11)$, as needed.

Case 3. All vertices of $V(G)\setminus V(P^{2}_{6})$ are adjacent to at most 3
vertices of $V(P^{2}_{6})$. By Lemma 16 again, it follows that $e(G)\leq
12+15+8=35<f_{C_{3}\square P_{2}}(11)$. In conclusion, we complete the proof
of (13) in the base case $n=11$.

§ Inductive Step §

In what follows, we will show the inductive step. Suppose that (11) holds for
all integers $\ell\leq n-1$ and $\ell\neq 5$. Now we consider the case $n\geq
7$. Assume that $G$ is a $C_{3}\square P_{2}$-free graph on $n$ vertices with
maximum number of edges. We need to show that $e(G)\leq f_{C_{3}\square
P_{2}}(n)$. Our inductive step will start from $n-6$ to $n$. Upon on
computations, we can obtain that

$f_{C_{3}\square P_{2}}(n)=f_{C_{3}\square P_{2}}(n-6)+3n-6.$ (14)

First of all, if $P^{2}_{6}\nsubseteq G$, then by Theorem 14, we get $e(G)\leq
f_{C_{3}\square P_{2}}(n)$, as desired. In what follows, we assume that
$P^{2}_{6}\subseteq G$, and then we will show a $\bm{stronger}$ result

$e(G)\leq f_{C_{3}\square P_{2}}(n)-1,$ (15)

except for $n=7,8$. By Lemma 17, there are at most $2$ vertices of
$V(G)\setminus V(P^{2}_{6})$ adjacent to exactly $4$ vertices of
$V(P^{2}_{6})$. In the sequel, we shall present the proof in three cases.

Case A. If there are exactly $2$ vertices of $V(G)\setminus V(P^{2}_{6})$, say
$x$ and $y$, adjacent to 4 vertices of $P^{2}_{6}$, then by Lemma 17, we get
either $H_{1}\subseteq G$ or $H_{2}\subseteq G$.

Subcase A.1. Assume that $H_{1}\subseteq G$. Then Lemma 18 gives
$e(G[V(P^{2}_{6})])\leq 10$.

If $e(G[V(P^{2}_{6})])\leq 9$, then $e(G)\leq
9+8+3(n-8)+\operatorname{ex}(n-6,C_{3}\square P_{2})\leq 3n-7+f_{C_{3}\square
P_{2}}(n-6)<f_{C_{3}\square P_{2}}(n)$, as needed. In what follows, we assume
that $e(G[V(P^{2}_{6})])=10$. Then Lemma 18 implies that $G[V(P_{6}^{2})]$
consists of $P_{6}^{2}$ by adding the edge $v_{3}v_{6}$.

If there exists a vertex of $V(G)\setminus(V(P^{2}_{6})\cup\\{x,y\\})$
adjacent to at most 2 vertices of $P^{2}_{6}$, then $e(G)\leq
10+8+2+3(n-9)+\operatorname{ex}(n-6,C_{3}\square P_{2})\leq
3n-7+f_{C_{3}\square P_{2}}(n-6)<f_{C_{3}\square P_{2}}(n)$, where the last
inequality holds by (14).

If all vertices of $V(G)\setminus(V(P^{2}_{6})\cup\\{x,y\\})$ are adjacent to
3 vertices of $P^{2}_{6}$, then it is easy to check that they have the same
neighbors on $P^{2}_{6}$; see $H_{3}$ in Figure 9. Next, we show that
$V(G)\setminus V(P_{6}^{2})$ is an independent set in $G$. Indeed, by Lemma
17, we know that $xy\notin E(G)$. In Figure 9, if $xz$ is an edge of $G$, then
combining with triangles $xv_{3}z,v_{4}v_{5}v_{6}$ with edges
$v_{3}v_{6},xv_{4},zv_{5}$, we see that $G$ has a copy of $C_{3}\square
P_{2}$, a contradiction. If $yz$ is an edge of $G$, then the triangles
$v_{3}yz,v_{4}v_{5}v_{6}$ and edges $v_{3}v_{4},yv_{5},zv_{6}$ form a copy of
$C_{3}\square P_{2}$, a contradiction. If $zw$ is an edge of $G$, then the
copy of $C_{3}\square P_{2}$ will appear on the triangles
$v_{3}zw,v_{4}v_{5}v_{6}$ and edges $v_{3}v_{4},zv_{5},wv_{6}$, a
contradiction. To sum up, we get that $G=H_{3}$; see Figure 9. Consequently,
we have $e(G)=10+8+3(n-8)<f_{C_{3}\square P_{2}}(n)$, as desired.

$v_{1}$$v_{2}$$v_{3}$$v_{4}$$v_{5}$$v_{6}$$x$$x$$y$$y$$z$$w$$H_{3}$$\cdots$$n-8$

$v_{1}$$v_{2}$$v_{3}$$v_{4}$$v_{5}$$v_{6}$$x$$x$$y$$y$$G_{3}$

Figure 9: The graphs $H_{3}$ and $G_{3}$, respectively.

Subcase A.2. Assume that $H_{2}\subseteq G$. By Lemma 19, we have
$e(G[V(P^{2}_{6})])\leq 11$.

If $e(G[V(P^{2}_{6})])\leq 9$, then $e(G)\leq
9+8+3(n-8)+\operatorname{ex}(n-6,C_{3}\square P_{2})\leq 3n-7+f_{C_{3}\square
P_{2}}(n-6)<f_{C_{3}\square P_{2}}(n)$, where the last inequality follows from
(14).

If $10\leq e(G[V(P^{2}_{6})])\leq 11$, then by the proof of Lemma 19, we know
that $v_{1}v_{4}\in E(G)$ or $v_{3}v_{6}\in E(G)$. We need to prove the
following cliam.

######  Claim 4.

If $H_{2}$ is a subgraph of $G$ and $z\in
V(G)\backslash(V(P_{6}^{2})\cup\\{x,y\\})$ is a vertex which is adjacent to
three vertices of $P_{6}^{2}$, then $zx\notin E(G)$ and $zy\notin E(G)$.

###### Proof of Claim.

The proof is straightforward. ∎

If $V(G)\setminus(V(P^{2}_{6})\cup\\{x,y\\})$ has a vertex, say $z$, which is
adjacent to at most $2$ vertices of $P^{2}_{6}$, then $e(G)\leq
11+8+2+3(n-9)+\operatorname{ex}(n-6,C_{3}\square P_{2})\leq
3n-6+f_{C_{3}\square P_{2}}(n-6)=f_{C_{3}\square P_{2}}(n)$. Next, we show
further that $e(G)<f_{C_{3}\square P_{2}}(n)$. Otherwise, if the equality
$e(G)=f_{C_{3}\square P_{2}}(n)$ holds, then the above inequalities must be
equalities. More precisely, we get $e(G[V(P^{2}_{6})])=11$, each vertex
outside of $V(P_{6}^{2})\cup\\{x,y,z\\}$ has exactly $3$ neighbors on
$P_{6}^{2}$, and the induced subgraph $G[V(G)\setminus V(P_{6}^{2})]$ is an
$(n-6)$-vertex extremal graph for $C_{3}\square P_{2}$. By Claim 4, we see
that each vertex outside of $V(P_{6}^{2})\cup\\{x,y,z\\}$ can not be adjacent
to any vertex of $\\{x,y\\}$. Consequently, in the subgraph $G[V(G)\setminus
V(P_{6}^{2})]$, the vertex $x$ (and $y$) has at most one neighbor, and the
only possible neighbor is $z$. However, by induction, we can see that the
extremal graphs for $C_{3}\square P_{2}$ do not contain any vertex with degree
at most one. This is a contradiction. In other words, the subgraph
$G[V(G)\setminus V(P_{6}^{2})]$ can not be an extremal graph for $C_{3}\square
P_{2}$. Then we get $e(G)<f_{C_{3}\square P_{2}}(n)$, as desired in (15).

If all vertices of $V(G)\setminus(V(P^{2}_{6})\cup\\{x,y\\})$ are adjacent to
3 vertices of $P^{2}_{6}$, then by Claim 4, there is no edge between
$\\{x,y\\}$ and $V(G)\setminus(V(P^{2}_{6})\cup\\{x,y\\})$. In other words,
$x,y$ are two isolated vertices in the induced subgraph $G[V(G)\setminus
V(P^{2}_{6})]$. Therefore, $e(G)\leq
11+8+3(n-8)+\operatorname{ex}(n-8,C_{3}\square P_{2})\leq 3n-5+f_{C_{3}\square
P_{2}}(n-8)<f_{C_{3}\square P_{2}}(n)$, where the second inequality follows by
induction whenever $n\neq 13$, and the last inequality holds for $n\neq 8$ by
a direct computation.

In particular, for $n=8$, we get $V(G)=V(P_{6}^{2})\cup\\{x,y\\}$ and

$e(G)\leq 11+8=19=f_{C_{3}\square P_{2}}(8),$ (16)

equality holds if and only if $G$ is obtained from $H_{2}$ by adding two edges
$v_{1}v_{4}$ and $v_{3}v_{6}$; see $G_{3}$ in Figure 9. In the equality case,
we get $G=G_{3}$ and $e(G_{3})=19=f_{C_{3}\square P_{2}}(8)$. In addition, for
$n=13$, recall in (12) that $\operatorname{ex}(5,C_{3}\square
P_{2})=e(K_{5})=10$, and then $e(G)\leq 11+8+3\times
5+\operatorname{ex}(5,C_{3}\square P_{2})=44<48=f_{C_{3}\square P_{2}}(13)$,
as needed.

Case B. If there is exactly one vertex $v\in V(G)\setminus V(P^{2}_{6})$
adjacent to 4 vertices of $P^{2}_{6}$, then by Claim 3, we know that $v$ is
one of the four types in Figure 7.

Firstly, we claim that $e(G[V(P^{2}_{6})])\leq 11$. Otherwise, if
$e(G[V(P^{2}_{6})])=12$, then Lemma 16 implies that $v_{2}v_{5},v_{2}v_{6}$
and $v_{3}v_{6}$ are edges of $G$. Note that the vertex set
$\\{v_{2},v_{3},\ldots,v_{6}\\}$ forms a copy of $K_{5}$ in $G$. Since $v$ has
$4$ neighbors on $P_{6}^{2}$, it follows that $v$ has at least $3$ neighbors
on this copy of $K_{5}$, which leads to a copy of $C_{3}\square P_{2}$ in $G$,
a contradiction.

Subcase B.1. If $v$ is of Type 2, Type 3 or Type 4 in Figure 7, then we can
show further that $e(G[V(P^{2}_{6})])\leq 10$. More precisely, if $v$ is of
Type 2, then adding any non-edge of $P_{6}^{2}$ to $G$ can make a copy of
$C_{3}\square P_{2}$, and so $e(G[V(P^{2}_{6})])=9$; if $v$ is of Type 3, then
$v_{2}v_{5}$ is the only possible edge of $G$, and hence
$e(G[V(P^{2}_{6})])\leq 10$; if $v$ is of Type 4, then $v_{3}v_{6}$ is the
only possible edge, and thus $e(G[V(P^{2}_{6})])\leq 10$. Therefore, we obtain
$e(G)\leq 10+4+3(n-7)+\operatorname{ex}(n-6,C_{3}\square P_{2})\leq
3n-7+f_{C_{3}\square P_{2}}(n-6)<f_{C_{3}\square P_{2}}(n)$.

Subcase B.2. Assume that $v$ is of Type 1 in Figure 7. In this type, we shall
show that

$v_{1}v_{5},v_{1}v_{6},v_{2}v_{5},v_{2}v_{6}\notin E(G).$ (17)

Indeed, if $v_{1}v_{5}\in E(G)$, then $G$ has a copy of $C_{3}\square P_{2}$,
which appears on the triangles $vv_{1}v_{2},v_{3}v_{4}v_{5}$ with the edges
$v_{1}v_{5},v_{2}v_{3},vv_{4}$. If $v_{1}v_{6}\in E(G)$, then the triangles
$vv_{1}v_{3},v_{4}v_{5}v_{6}$ and the edges $v_{1}v_{6},v_{3}v_{5},vv_{4}$
form a copy of $C_{3}\square P_{2}$ in $G$. If $v_{2}v_{5}\in E(G)$, then $G$
contains a copy of $C_{3}\square P_{2}$ consisting of the triangles
$vv_{1}v_{2},v_{3}v_{4}v_{5}$ and the edges $v_{1}v_{3},v_{2}v_{5},vv_{4}$. If
$v_{2}v_{6}\in E(G)$, then $C_{3}\square P_{2}\subseteq G$ by combining the
triangles $vv_{2}v_{3},v_{4}v_{5}v_{6}$ with the edges
$v_{2}v_{6},v_{3}v_{5},vv_{4}$. This completes the proof of (17). Therefore,
to avoid a copy of $C_{3}\square P_{2}$ in $G$, the possible edges on
$V(P_{6}^{2})$ are $v_{1}v_{4}$ and $v_{3}v_{6}$; see Figure 10.

$v_{1}$$v_{2}$$v_{3}$$v_{4}$$v_{5}$$v_{6}$$v$ Figure 10: $v$ is of Type 1 and
$e(G[V(P_{6}^{2})])=11$

First of all, if $e(G[V(P^{2}_{6})])\leq 10$, then $e(G)\leq
10+4+3(n-7)+\operatorname{ex}(n-6,C_{3}\square P_{2})\leq 3n-7+f_{C_{3}\square
P_{2}}(n-6)<f_{C_{3}\square P_{2}}(n)$, as required. Next, we assume that
$e(G[V(P^{2}_{6})])=11$. By (17), we know that $v_{1}v_{4},v_{3}v_{6}\in
E(G)$; see Figure 10.

If there exist a vertex of $V(G)\setminus(V(P^{2}_{6})\cup\\{v\\})$ adjacent
to at most $2$ vertices of $P^{2}_{6}$, then there are at most $4+2+3(n-8)$
edges between $V(P_{6}^{2})$ and $V(G)\setminus V(P_{6}^{2})$. Thus, we get
$e(G)\leq 11+4+2+3(n-8)+\operatorname{ex}(n-6,C_{3}\square P_{2})\leq
3n-7+f_{C_{3}\square P_{2}}(n-6)<f_{C_{3}\square P_{2}}(n)$.

If all vertices of $V(G)\setminus(V(P^{2}_{6})\cup\\{v\\})$ are adjacent to
$3$ vertices of $P^{2}_{6}$, then there are exactly $4+3(n-7)$ edges between
$V(P_{6}^{2})$ and $V(G)\setminus V(P_{6}^{2})$. Since each vertex $x\in
V(G)\setminus(V(P^{2}_{6})\cup\\{v\\})$ has $3$ neighbors on $P_{6}^{3}$, we
can check that $vx\notin E(G)$. Otherwise, one can find a copy of
$C_{3}\square P_{2}$ in $G$. Therefore, $v$ is an isolated vertex in the
induced subgraph $G[V(G)\setminus V(P_{6}^{2})]$. Then $e(G)\leq
11+4+3(n-7)+\operatorname{ex}(n-7,C_{3}\square P_{2})\leq 3n-6+f_{C_{3}\square
P_{2}}(n-7)<f_{C_{3}\square P_{2}}(n)$, where the second inequality follows by
induction whenever $n\neq 12$, and the last inequality holds for $n\neq 7$ by
calculations.

In particular, for $n=7$, we have $V(G)=V(P_{6}^{2})\cup\\{v\\}$ and

$e(G)\leq 11+4=15=f_{C_{3}\square P_{2}}(7),$ (18)

where equality holds if and only if $G$ is a graph of Type 1 by adding edges
$v_{1}v_{4}$ and $v_{3}v_{6}$; see Figure 10. In the equality case, we see
that $G=G_{2}$ and $e(G_{2})=15=f_{C_{3}\square P_{2}}(7)$. Moreover, for
$n=12$, recall in (12) that $\mathrm{ex}(5,C_{3}\square P_{2})=e(K_{5})=10$,
then we have $e(G)\leq 11+4+3\times 5+\mathrm{ex}(5,C_{3}\square
P_{2})=40<42=f_{C_{3}\square P_{2}}(12)$, as desired in (15).

Case C. Assume that $V(G)\setminus V(P_{6}^{2})$ has no vertex which has $4$
neighbors on $P_{6}^{2}$. By Lemma 16, we have $e(G[V(P_{6}^{2})])\leq 12$. We
show the proof in two subcases.

Subcase C.1. There is a vertex of $V(G)\setminus V(P^{2}_{6})$ adjacent to at
most 2 vertices of $P^{2}_{6}$, then the number of edges between
$V(P_{6}^{2})$ and $V(G)\setminus V(P_{6}^{2})$ is at most $2+3(n-7)$ since
the other vertices of $V(G)\setminus V(P_{6}^{2})$ adjacent to at most 3
vertices of $P^{2}_{6}$. Thus, we get $e(G)\leq
12+2+3(n-7)+\operatorname{ex}(n-6,C_{3}\square P_{2})\leq 3n-7+f_{C_{3}\square
P_{2}}(n-6)<f_{C_{3}\square P_{2}}(n)$.

Subcase C.2. All vertices of $V(G)\setminus V(P^{2}_{6})$ are adjacent to
exactly 3 vertices of $P^{2}_{6}$.

If $e(G[V(P^{2}_{6})])\leq 11$, then $e(G)\leq
11+3(n-6)+\operatorname{ex}(n-6,C_{3}\square P_{2})\leq 3n-7+f_{C_{3}\square
P_{2}}(n-6)<f_{C_{3}\square P_{2}}(n)$, where the second inequality holds by
induction.

If $e(G[V(P^{2}_{6})])=12$, then by Lemma 16, we know that
$G[V(P_{6}^{2})]=G_{1}$, and so $v_{2}v_{5},v_{2}v_{6}$ and $v_{3}v_{6}$ are
edges of $G$. Note that $G[\\{v_{2},v_{3},\ldots,v_{6}\\}]$ forms a copy of
$K_{5}$; see Figure 11. We next show that for every $y\in V(G)\setminus
V(P_{6}^{2})$,

$N_{P_{6}^{2}}(y)=\\{v_{1},v_{2},v_{3}\\}.$ (19)

Choosing any vertex $x\in V(G)\setminus V(P_{6}^{2})$. If
$N_{P_{6}^{2}}(x)\subseteq\\{v_{2},v_{3},\ldots,v_{6}\\}$, say
$N_{P_{6}^{2}}(x)=\\{v_{3},v_{4},v_{5}\\}$ by symmetry, then $G$ contains a
copy of $C_{3}\square P_{2}$, which consists of the triangles
$xv_{3}v_{4},v_{2}v_{5}v_{6}$ and the edges $xv_{5},v_{3}v_{2},v_{4}v_{6}$, a
contradiction. Hence, we get
$N_{P_{6}^{2}}(x)\nsubseteq\\{v_{2},v_{3},\ldots,v_{6}\\}$. Without loss of
generality, we may assume that $x\in V(G)\setminus V(P_{6}^{2})$ is a vertex
with $N_{P_{6}^{2}}(x)=\\{v_{1},v_{2},v_{3}\\}$. Moreover, if $V(G)\setminus
V(P_{6}^{2})$ contains a vertex $y$ differing from $x$ such that
$N_{P_{6}^{2}}(y)\neq N_{P_{6}^{2}}(x)$, then by symmetry, we assume that
either $N_{P_{6}^{2}}(y)=\\{v_{1},v_{2},v_{4}\\}$ or
$N_{P_{6}^{2}}(y)=\\{v_{1},v_{4},v_{5}\\}$. In the former case, it is easy to
see that the triangles $xv_{1}v_{3},yv_{2}v_{4}$ and the edges
$xv_{2},v_{1}y,v_{3}v_{4}$ form a copy of $C_{3}\square P_{2}$. In fact, one
can find another copy without the use the vertex $x$ by combining two
triangles $yv_{1}v_{2},v_{3}v_{4}v_{5}$ with edges
$yv_{4},v_{1}v_{3},v_{2}v_{5}$. In the latter case, we also see that $G$ has a
copy of $C_{3}\square P_{2}$ consisting of the triangles
$v_{1}v_{2}v_{3},yv_{4}v_{5}$ and the edges $v_{1}y,v_{2}v_{4},v_{3}v_{5}$.
This is a contradiction. Consequently, we complete the proof of (19) and
$H_{4}\subseteq G$; see Figure 11.

$v_{1}$$v_{2}$$v_{3}$$v_{4}$$v_{5}$$v_{6}$$\cdots$$n-6$$x$$y$$H_{4}$ Figure
11: The graph $H_{4}$.

Since $v_{1}v_{2}v_{3}$ is a triangle, to avoid a copy of $C_{3}\square P_{2}$
in $G$, we obtain that $G[V(G)\setminus V(P^{2}_{6})]$ is triangle-free.
Hence, by Mantel’s result (1), we have $e(G)\leq
12+3(n-6)+\lfloor\frac{(n-6)^{2}}{4}\rfloor=3n-6+\lfloor\frac{(n-6)^{2}}{4}\rfloor<f_{C_{3}\square
P_{2}}(n)$, as required. In a word, we complete the proof of (15). ∎

In fact, our proof of Theorem 2 implies the following stronger result.

######  Theorem 20.

Let $n\geq 9$ be an integer. If $G$ is a graph with maximum number of edges
over all $C_{3}\square P_{2}$-free graphs on $n$ vertices, then $G$ is an
extremal graph for $P_{6}^{2}$.

###### Proof.

Recalling the proof of (15), we are done. ∎

Combining with Theorem 15, we give the extremal graphs for $C_{3}\square
P_{2}$.

###### Proof of Theorem 3.

Let $G$ be an $n$-vertex $C_{3}\square P_{2}$-free graph with maximum number
of edges. In other words, $e(G)=\mathrm{ex}(n,C_{3}\square
P_{2})=f_{C_{3}\square P_{2}}(n)$. For $n=6$, if $G$ contains $P_{6}^{2}$ as a
subgraph, then by Lemma 16, we have $e(G)=12$ and $G=G_{1}$; if $G$ is
$P_{6}^{2}$-free, then by Theorem 15, we get $G=H_{6}^{3}$. For $n=7$, if $G$
contains $P_{6}^{2}$ as a subgraph, then the proof of (18) implies that
$G=G_{2}$; if $G$ is $P_{6}^{2}$-free, then applying Theorem 15, we obtain
$G\in\\{F_{7}^{4,1},F_{7}^{4,4},H_{7}^{3}\\}$. For $n=8$, if $G$ has a copy of
$P_{6}^{2}$, then the proof of (16) implies that $G=G_{3}$; if $G$ is
$P_{6}^{2}$-free, then Theorem 15 gives that
$G\in\\{F_{8}^{4,1},F_{8}^{4,4},F_{8}^{5,2},F_{8}^{5,5}\\}$.

When $n\geq 9$, Theorem 20 asserts that $G$ is an extremal graph for
$P_{6}^{2}$. Indeed, if $P_{6}^{2}\subseteq G$, then by (15) we know that
$e(G)\leq f_{C_{3}\square P_{2}}(n)-1$, a contradiction. Therefore, using
Theorem 15 again, we can obtaine all extremal graph for $C_{3}\square P_{2}$
immediately. ∎

##  6 Concluding remarks

In Theorem 1, we determined the Turán number $\mathrm{ex}(n,C_{2k+1}\square
P_{2})$ and characterized the corresponding extremal graphs for fixed $k\geq
1$ and sufficiently large $n$.

Note that $C_{2k}\square P_{2}$ is a bipartite graph, and it is a regular
graph with degree $3$. For such a spare bipartite graph, we can obtain that
for every $k\geq 2$,

$\mathrm{ex}(n,C_{2k}\square P_{2})=O(n^{5/3}).$ (20)

Indeed, it can be derived from a result of Füredi [21] that if $H$ is a
bipartite graph with maximum degree at most $d$ on one side of the
bipartition, then $\mathrm{ex}(n,H)=O(n^{2-1/d})$. In 2003, Alon, Krivelevich
and Sudakov [1] provided another alternative proof of such a result as one of
the applications of the celebrated dependent random choice method; see, e.g.,
[20] for a description of this powerful probabilistic technique. It seems
extremely difficult to determine the magnitude of the Turán number of
$C_{2k}\square P_{2}$. For example, in the case $k=2$, it reduces to the cube
$Q_{8}$, Simonovits [18] proved in 1970 that
$\mathrm{ex}(n,Q_{8})=O(n^{8/5})$. Until now, it remains unknown whether
$\mathrm{ex}(n,Q_{8})=\Theta(n^{8/5})$. Recently, Conlon and Lee [8]
conjectured that if $H$ is a bipartite graph with maximum degree at most $d$
on one side, and $H$ is $K_{d,d}$-free, then
$\mathrm{ex}(n,H)=O(n^{2-1/d-\varepsilon})$ holds for some
$\varepsilon=\varepsilon(H)>0$; see [8, 30] for proofs of the case $d=2$, and
[9, 43] for more related results. Observe that $C_{2k}\square P_{2}$ is
$K_{3,3}$-free. Motivated by the above works, we would like to propose the
following conjecture, which generalized the bound in (20) exponentially.

######  Conjecture 21.

For every $k\geq 2$, there exists $\varepsilon=\varepsilon(k)>0$ such that

$\mathrm{ex}(n,C_{2k}\square P_{2})=O(n^{\frac{5}{3}-\varepsilon}).$

Finally, we conclude this paper with a new conjecture proposed by Bradač,
Janzer, Sudakov and Tomon [4] on the study of Turán number of the grid
$P_{t}\square P_{t}$.

######  Conjecture 22 (See [4]).

Let $T,S$ be any two trees with at least one edge. There exist positive real
numbers $c$ and $C$ such that

$cn^{3/2}\leq\mathrm{ex}(n,T\square S)\leq Cn^{3/2}.$

## Declaration of competing interest

The authors declare that they have no conflicts of interest to this work.

## Acknowledgments

This work was supported by NSFC (Nos. 12271527, 12071484, 11931002), Natural
Science Foundation of Hunan Province (Nos. 2020JJ4675, 2021JJ40707) and the
Fundamental Research Funds for the Central Universities of Central South
University (Grant No. 2021zzts0034).

## References

  * [1] N. Alon, M. Krivelevich, B. Sudakov, Turán numbers of bipartite graphs and related Ramsey-type questions, Combin. Probab. Comput. 12 (2003) 477–494.
  * [2] H. Bielak, Kieliszek, The Turán number of the graph $2P_{5}$, Discuss. Math. Graph Theory. 36 (3) (2016) 683–694.
  * [3] B. Bollobás, Extremal Graph Theory, Academic Press, New York, 1978.
  * [4] D. Bradač, O. Janzer, B. Sudakov, I. Tomon, The Turán number of the grid, Bull. London Math. Soc. (2022), online, See https://doi.org/10.1112/blms.12721.
  * [5] N. Bushaw, N. Kettle, Turán numbers of multiple paths and equibipartite forests, Combin. Probab. Comput. 20 (2011) 837–853.
  * [6] V. Campos, R. Lopes, A proof for a conjecture of Gorgol, Discrete Appl. Math. 245 (2018) 202–207.
  * [7] G. Chen, R.J. Gould, F. Pfender, B. Wei, Extremal graphs for intersecting cliques, J. Combin. Theory. Ser. B 89 (2003) 159–171.
  * [8] D. Conlon, J. Lee, On the extremal number of subdivisions, Int. Math. Res. Not. IMRN 12 (2021) 9122–9145.
  * [9] D. Conlon, O. Janzer, J. Lee, More on the extremal number of subdivisions, Combinatorica 41 (4) (2021) 465–494.
  * [10] G. Dirac, Extensions of Turán’s theorem on graphs, Acta Math. Acad. Sci. Hungar. 14 (1963) 417–422.
  * [11] T. Dzido, A note on Turán numbers for even wheels, Graphs and Combin. 29 (2013) 1305–1309.
  * [12] T. Dzido, A. Jastrzebski, Turán Numbers for odd wheels, Discrete Math. 341 (4) (2018) 1150–1154.
  * [13] P. Erdős, On some new inequalities concerning extremal properties of graphs, stability problems, Theory Graphs (Proc. Colloq. Tihany, 1966) (1968) 77–81.
  * [14] P. Erdős, Z. Füredi, R.J. Gould, D.S. Gunderson, Extremal graphs for intersecting triangles, J. Combin. Theory Ser. B 64 (1) (1995) 89–100.
  * [15] P. Erdős, T. Gallai, On maximal paths, circuits of graphs, Acta Math. Acad. sci. Hungar. 10 (1959) 337–356.
  * [16] P. Erdős, A.H. Stone, On the structure of linear graphs, Bull. Amer. Math. Soc. 52 (1946) 1087–1091.
  * [17] P. Erdős, M. Simonovits, A limit theorem in graph theory, Studia Sci. Math. Hungar. 1 (1966) 51–57.
  * [18] P. Erdős, M. Simonovits, Some extremal problems in graph theory. Combinatorial theory and its applications, I (Proc. Colloq., Balatonfüred, 1969), North-Holland, Amsterdam, 1970, pp. 377–390.
  * [19] P. Erdős, M. Simonovits, An extremal graph problem, Acta Math. Acad. Sci. Hungar. 22 (1971/72) 275–282.
  * [20] J. Fox, B. Sudakov, Dependent random choice, Random Structures Algorithms 38 (2011) 68–99.
  * [21] Z. Füredi, On a Turán type problem of Erdős, Combinatorica 11 (1991) 75–79.
  * [22] Z. Füredi, D.S. Gunderson, Extremal numbers for odd cycles, Combin. Probab. Comput. 24 (4) (2015) 641–645.
  * [23] Z. Füredi, A. Kostochka, J. Verstraëte, Stability in the Erdős–Gallai theorems on cycles and paths, J. Combin. Theory Ser. B 121 (2016) 197–228.
  * [24] Z. Füredi, A. Kostochka, R. Luo, J. Verstraëte, Stability in the Erdős–Gallai theorem on cycles and paths II, Discrete Math. 341 (2018) 1253–1263.
  * [25] Z. Füredi, On a theorem of Erdős and Simonovits on graphs not containing the cube, in Number Theory, Analysis, and Combinatorics, Proceedings of the Paul Turán Memorial Conference, Budapest, 2013, pp. 113–125. See https://arxiv.org/abs/1307.1062.
  * [26] Z. Füredi, M. Simonovits, The history of degenerate (bipartite) extremal graph problems, in Erdős centennial, Bolyai Soc. Math. Stud., 25, János Bolyai Math. Soc., Budapest, 2013, pp. 169–264. See https://arxiv.org/abs/1306.5167v2.
  * [27] R.J. Faudree, R.H. Schelp, Path Ramsey numbers in multicolorings, J. Combin. Theory. Ser. B 19 (1975) 150–160.
  * [28] X. Hou, Y. Qiu, B. Liu, Extremal graph for intersecting odd cycles, Electron. J. Combin. 23 (2) (2016) P2.29.
  * [29] X. Hou, Y. Qiu, B. Liu, Turán number and decomposition number of intersecting odd cycles, Discrete Math. 341 (2018) 126–137.
  * [30] O. Janzer, Improved bounds for the extremal number of subdivisions, Electron. J. Combin. 26 (2019) Paper No. 3.3.
  * [31] G.N. Kopylov, Maximal paths, cycles in a graph, Dokl. Akad. Nauk SSSR, 234 (1) (1977) 19–21. English translation: Soviet Mathh. Dokl. 18(3), (1977) 593–596.
  * [32] Y. Lan, Z. Qin, Y. Shi, The Turán number for $2P_{7}$, Discuss. Math. Graph Theory. 39 (2019) 805–814.
  * [33] H. Liu, Extremal graphs for blow-ups of cycles, trees, Electron. J. Combin. 20 (1) (2013), P65.
  * [34] J. Ma, B. Ning, Stability results on the circumference of a graph, Combinatorica 40 (1) (2020) 105–147.
  * [35] W. Mantel: Problem 28, soln. by H. Gouventak, W. Mantel, J. Teixeira de Mattes, F. Schuh, W.A. Wythoff. Wiskundige Opgaven 10 (1907) 60–61.
  * [36] Z. Ni, L. Kang, E. Shan, H. Zhu, Extremal graphs for blow-ups of keyrings, Graphs and Combin. 36 (2020) 1827–1853.
  * [37] R. Pinchasi, M. Sharir, On graphs that do not contain the cube and related problems, Combinatorica 25 (2005) 615–623.
  * [38] M. Simonovits, A method for solving extremal problems in graph theory, stability problems, Theory of Graphs (Proc. Colloq., Tihany, 1966) (1968) 279–319.
  * [39] M. Simonovits, Extremal graph problems with symmetrical extremal graphs, additionnal chromatic conditions, Discrete Math. 7 (1974) 349–376.
  * [40] M. Simonovits, The extremal graph problem of the icosahedron, J. Combin. Theory Ser. B 17 (1974), 69–79.
  * [41] M. Simonovits, Extremal problems, graph products, Studies in Pure Mathematics, pp. 669–680, Akadémiai Kiadó, Birkhäuser Verlag 1982.
  * [42] M. Simonovits, Paul Erdős’ influence on extremal graph theory, in The Mathematics of Paul Erdős II, R.L. Graham, Springer, New York, 2013, pp. 245–311.
  * [43] B. Sudakov, I. Tomon, Turán number of bipartite graphs with no $K_{t,t}$, Proc. Amer. Math. Soc. 148 (7) (2020) 2811–2818.
  * [44] P. Turán, On an extremal problem in graph theory, Mat. Fiz. Lapok 48 (1941), pp. 436–452. (in Hungarian).
  * [45] C. Xiao, G.O.H. Katona, J. Xiao, O. Zamora, The Turán number of the square of a path, Discrete Appl. Math. 307 (2022) 1–14.
  * [46] L.-T. Yuan, X.-D. Zhang, The Turán number of disjoint copies of paths, Discrete Math. 340 (2) (2017) 132–139.
  * [47] L.-T. Yuan, X.-D. Zhang, Turán numbers for disjoint paths, J. Graph Theory 98 (3) (2021) 499–524.
  * [48] L.-T. Yuan, Extremal graphs for the $k$-flower, J. Graph Theory 89 (2018) 26–39.
  * [49] L.-T. Yuan, Extremal graphs for odd wheels, J. Graph Theory 98 (2021) 691–707.
  * [50] L.-T. Yuan, Extremal graphs for edge-blow up of graphs, J. Combin. Theory Ser. B 152 (2022) 379–398.
  * [51] L.-T. Yuan, Extremal graphs of the $p$-th power of paths, European J. Combin. 104 (2022) 103548.