The Erds-Sós Conjecture for Graphs Whose Complements Contain No C_4  

作　　者：Jian-huaYin Jiong-shengLi 

机构地区：[1]DepartmentofAppliedMathematics,CollegeofInformationScienceandTechnology,HainanUniversity,Haikou570228,China [2]DepartmentofMathematics,UniversityofScienceandTechnologyofChina,Hefei230026,China

出　　处：《Acta Mathematicae Applicatae Sinica》2004年第3期397-400,共4页应用数学学报（英文版）

基　　金：Supported by the National Natural Science Foundation of China (No.19971086);the Doctoral Foundation of Hainan University

摘　　要：Erds and Sós conjectured in 1963 (see [1],Problem 12 in 247) that every graph G on n verticeswith size e(G)>1/2n(k-1) contains every tree T of size k.In this paper,we prove the conjecture for graphswhose complements contain no cycles of length 4.Erds and Sós conjectured in 1963 (see [1],Problem 12 in 247) that every graph G on n verticeswith size e(G)>1/2n(k-1) contains every tree T of size k.In this paper,we prove the conjecture for graphswhose complements contain no cycles of length 4.

关 键 词：Graph tree packing 

分 类 号：O157.5[理学—数学]