On Turán Number of Graphs with Small Minimum Feedback Vertex Numbers

Abstract

Given a graph $H$, the minimum feedback vertex number of $H$ is the minimum number of vertices whose removal results in an acyclic graph. In this paper, we investigate Turán-type extremal problems for bipartite graphs in terms of their feedback vertex number. Our first result concerns bipartite graphs $H$ with minimum feedback vertex number one. Such graphs can be obtained from a forest by identifying a specified collection of leaves into a single vertex. For these graphs, we show that $\text{ex}(n,H)$ is upper bounded by $O(n^{1+1/k^{\ast }})$, where $2k^{\ast }$ is the length of the shortest cycle contained in $H$. In addition, we consider a family of bipartite graphs with minimum feedback vertex number three. Let $E_{k,t}$ be the graph obtained from the theta graph ${\theta }_{k,t}$ by joining a new vertex $x$ to one side of the bipartition and another vertex $y$ to the other. Let $E_{k,t}^{+}$ denote the graph obtained by adding the edge $xy$ to $E_{k,t}$. We prove that for any $k\ge 2$ and sufficiently large $t$, $\text{ex}(n,E_{k,t}^{+})=\Theta (n^{\frac{3k-1}{2k-1}}).$

23 pages, 1 figure