The generalized Tur'{a}n number of long cycles in graphs and bipartite graphs

Abstract

Given a graph $T$ and a family of graphs $\mathcal{F}$, the maximum number of copies of $T$ in an $\mathcal{F}$-free graph on $n$ vertices is called the generalized Turán number, denoted by $ex(n,T,\mathcal{F})$. When $T=K_2$, it reduces to the classical Turán number $ex(n,\mathcal{F})$. Let $e{x}_{bip}(b,n,T,\mathcal{F})$ be the maximum number of copies of $T$ in an $\mathcal{F}$-free bipartite graph with two parts of sizes $b$ and $n$, respectively. Let $P_k$ be the path on $k$ vertices, ${\mathcal{C}}_{\ge k}$ be the family of all cycles with length at least $k$ and $M_k$ be a matching with $k$ edges. In this article, we determine $e{x}_{bip}(b,n,K_{s,t},{\mathcal{C}}_{\ge 2n-2k})$ exactly in a connected bipartite graph $G$ with minimum degree $\hat{I}´(G)\ge r\ge 1$, for $b\ge n\ge 2k+2r$ and $k\in \mathbb{Z}$, which generalizes a theorem of Moon and Moser, a theorem of Jackson and gives an affirmative evidence supporting a conjecture of Adamus and Adamus. As corollaries of our main result, we determine $e{x}_{bip}(b,n,K_{s,t},P_{2n-2k})$ and $e{x}_{bip}(b,n,K_{s,t},M_{n-k})$ exactly in a connected bipartite graph $G$ with minimum degree $\hat{I}´(G)\ge r\ge 1$, which generalizes a theorem of Wang. Moreover, we determine $ex(n,K_{s,t},{\mathcal{C}}_{\ge k})$ and $ex(n,K_{s,t},P_k)$ respectively in a connected graph $G$ with minimum degree $\hat{I}´(G)\ge r\ge 1$, which generalizes a theorem of Lu, Yuan and Zhang.

19 pages