Bipartite Version of the Erd\H{o}s-S\'{o}s Conjecture
Received:November 29, 2018  Revised:March 03, 2019
Key Word: Erd\H{o}s-S\'{o}s conjecture   bipartite graphs   trees
Fund ProjectL:Supported by the National Natural Science Foundation of China (Grant No.11671376), the Natural Science Foundation of Anhui Province (Grant No.1708085MA18) and Anhui Initiative in Quantum Information Technologies (Grant No.AHY150200).
 Author Name Affiliation Xinmin HOU School of Mathematical Sciences, University of Science and Technology of China, Anhui 230026, P. R. China Chenhui LU School of Mathematical Sciences, University of Science and Technology of China, Anhui 230026, P. R. China
Hits: 677
The Erd\H{o}s-S\'{o}s Conjecture states that every graph on $n$ vertices and more than $\frac{n(k-2)}{2}$ edges contains every tree of order $k$ as a subgraph. In this note, we study a weak (bipartite) version of Erd\H{o}s-S\'{o}s Conjecture. Based on a basic lemma, we show that every bipartite graph on $n$ vertices and more than $\frac{n(k-2)}{2}$ edges contains the following families of trees of order $k$: (1) trees of diameter at most five; (2) trees with maximum degree at least $\lfloor \frac{k-1}{2}\rfloor$; (3) almost balanced trees, these results are better than the corresponding known results for the general version of the Erd\H{o}s-S\'{o}s Conjecture.