The bipartite Turan number and spectral extremum for linear forests

Abstract

The bipartite Turán number of a graph $H$, denoted by $ex(m,n;H)$, is the maximum number of edges in any bipartite graph $G=(X,Y;E)$ with $|X|=m$ and $|Y|=n$ which does not contain $H$ as a subgraph. In this paper, we determined $ex(m,n;F_{\ell })$ for arbitrary $\ell$ and appropriately large $n$ with comparing to $m$ and $\ell$, where $F_{\ell }$ is a linear forest which consists of $\ell$ vertex disjoint paths. Moreover, the extremal graphs have been characterized. Furthermore, these results are used to obtain the maximum spectral radius of bipartite graphs which does not contain $F_{\ell }$ as a subgraph and characterize all extremal graphs which attain the maximum spectral radius.

18 pages