Discussion On The Erd(?)s-Sós Conjecture For Bipartite Graphs |
Posted on:2020-05-30 | Degree:Master | Type:Thesis |
Country:China | Candidate:C H Lv | Full Text:PDF |
GTID:2370330575464551 | Subject:Applied Mathematics |
Abstract/Summary: | PDF Full Text Request |
A famous conjecture on extremal graph theory is the Erd(?)s-Sós conjecture:if a graph G on n vertices has more than n(k-2)/2 edges then G contains every tree with k vertices.Motivated by the property of trees that every tree is a connected bipartite graph,we add bipartite graph condition on the graph G.Under the bipartite graph condition,we proved the following kinds of trees are subgraphs of G:(1)trees of diameter 5;(2)trees with maximum degree no less than?k-1/2?;(3)trees whose bipartition are almost balanced;(4)trees of diameter no less than k-4.We also proved the Erd(?)s-Sós conjecture when G is a bipartite graph and k?12.An interesting discovery even is a subgraph of G then so do any tree of order k with diameter odd.These results are better than the corresponding known results for the general version of the Erd(?)s-Sós Conjecture.The main tools used in this paper are embedding.The motivation for this approach comes from a basic observation:if the average degree of a graph is more than k-2,then it contains a subgraph with average degree more than k-2 and with minimal degree no less than?k/2?. |
Keywords/Search Tags: | Erd(?)s-Sós Conjecture, bipartite graphs, trees, embedding, minimal degree |
PDF Full Text Request |
Related items |