A Variation of a Conjecture Due to Erds and Sós  

作　　者：Jian Hua YIN Jiong Sheng LI 

机构地区：[1]Department of Mathematics, School of Information Science and Technology, Hainan University, Haikou 570228, P.R. China [2]Department of Mathematics, University of Science and Technology of China, Hefei 230026, P.R. China

出　　处：《Acta Mathematica Sinica,English Series》2009年第5期795-802,共8页数学学报（英文版）

基　　金：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.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.

关 键 词：GRAPH degree sequence Erdoes-Soes conjecture 

分 类 号：O157.5[理学—数学] F279.241[理学—基础数学]