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 NameAffiliation
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: 187
Download times: 215
Abstract:
      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.
Citation:
DOI:10.3770/j.issn:2095-2651.2019.03.003
View Full Text  View/Add Comment  Download reader