Bipartite Version of the Erd\H{o}sS\'{o}s Conjecture 
Received:November 29, 2018 Revised:March 03, 2019 
Key Word:
Erd\H{o}sS\'{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). 

Hits: 677 
Download times: 610 
Abstract: 
The Erd\H{o}sS\'{o}s Conjecture states that every graph on $n$ vertices and more than $\frac{n(k2)}{2}$ edges contains every tree of order $k$ as a subgraph. In this note, we study a weak (bipartite) version of Erd\H{o}sS\'{o}s Conjecture. Based on a basic lemma, we show that every bipartite graph on $n$ vertices and more than $\frac{n(k2)}{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{k1}{2}\rfloor$; (3) almost balanced trees, these results are better than the corresponding known results for the general version of the Erd\H{o}sS\'{o}s Conjecture. 
Citation: 
DOI:10.3770/j.issn:20952651.2019.03.003 
View Full Text View/Add Comment Download reader 