The Erdos-Sos conjecture says that a graph G on n vertices and number of edges e（G） 〉 n（k - 1）/2 contains all trees of size k. In this paper we prove a sufficient condition for a graph to contain every tree of si...The Erdos-Sos conjecture says that a graph G on n vertices and number of edges e（G） 〉 n（k - 1）/2 contains all trees of size k. In this paper we prove a sufficient condition for a graph to contain every tree of size k formulated in terms of the minimum edge degree ξ（G） of a graph G defined as {（G） = min{d（u） ＋ d（v） - 2 ： uv ∈ E（G）}. More precisely, we show that a connected graph G with maximum degree △（G） ≥ k and minimum edge degree {（G） 〉 2k - 4 contains every tree of k edges if dG（x） ＋ dG（y） ≥ 2k - 4 for all pairs x, y of nonadjacent neighbors of a vertex u of dG（u） ≥ k.展开更多
文摘The Erdos-Sos conjecture says that a graph G on n vertices and number of edges e（G） 〉 n（k - 1）/2 contains all trees of size k. In this paper we prove a sufficient condition for a graph to contain every tree of size k formulated in terms of the minimum edge degree ξ（G） of a graph G defined as {（G） = min{d（u） ＋ d（v） - 2 ： uv ∈ E（G）}. More precisely, we show that a connected graph G with maximum degree △（G） ≥ k and minimum edge degree {（G） 〉 2k - 4 contains every tree of k edges if dG（x） ＋ dG（y） ≥ 2k - 4 for all pairs x, y of nonadjacent neighbors of a vertex u of dG（u） ≥ k.
