Bipartite Version of the Erd\H{o}s-S\'{o}s Conjecture |
Received:November 29, 2018 Revised:March 03, 2019 |
Key Words:
Erd\H{o}s-S\'{o}s conjecture bipartite graphs trees
|
Fund Project: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: 1176 |
Download times: 852 |
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 |