Erdoes and Soes conjectured in 1963 that every graph G on n vertices with edge number e（G） 〉 1/2（k - 1）n contains every tree T with k edges as a subgraph. In this paper, we consider a variation of the above conje...Erdoes and Soes conjectured in 1963 that every graph G on n vertices with edge number e（G） 〉 1/2（k - 1）n contains every tree T with k edges as a subgraph. In this paper, we consider a variation of the above conjecture, that is, for n 〉 9/ 2k^2 ＋ 37/2＋ 14 and every graph G on n vertices with e（G） 〉 1/2 （k- 1）n, we prove that there exists a graph G＇ on n vertices having the same degree sequence as G and containing every tree T with k edges as a subgraph.展开更多
For A Zm and n ∈ Zm, let σA（n） be the number of solutions of equation n =x ＋ y, x, y ∈ A. Given a positive integer m, let Rm be the least positive integer r such that there exists a set A Zm with A ＋ A = Zm ...For A Zm and n ∈ Zm, let σA（n） be the number of solutions of equation n =x ＋ y, x, y ∈ A. Given a positive integer m, let Rm be the least positive integer r such that there exists a set A Zm with A ＋ A = Zm and σA（n） ≤ r. Recently, Chen Yonggao proved that all Rm ≤ 288. In this paper, we obtain new upper bounds of some special type Rkp2.展开更多
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.展开更多
基金Supported by National Natural Science Foundation of China (Nos. 10861006, 10401010)
文摘Erdoes and Soes conjectured in 1963 that every graph G on n vertices with edge number e（G） 〉 1/2（k - 1）n contains every tree T with k edges as a subgraph. In this paper, we consider a variation of the above conjecture, that is, for n 〉 9/ 2k^2 ＋ 37/2＋ 14 and every graph G on n vertices with e（G） 〉 1/2 （k- 1）n, we prove that there exists a graph G＇ on n vertices having the same degree sequence as G and containing every tree T with k edges as a subgraph.
基金Supported by the National Natural Science Foundation of China (Grant Nos. 10901002 10771103)
文摘For A Zm and n ∈ Zm, let σA（n） be the number of solutions of equation n =x ＋ y, x, y ∈ A. Given a positive integer m, let Rm be the least positive integer r such that there exists a set A Zm with A ＋ A = Zm and σA（n） ≤ r. Recently, Chen Yonggao proved that all Rm ≤ 288. In this paper, we obtain new upper bounds of some special type Rkp2.
文摘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.
