On the Erdos- Sos Conjecture for graphs on n = k+4 vertices

被引：0
作者：
Yuan, Long-Tu [1 ]
Zhang, Xiao-Dong
机构：
[1] Shanghai Jiao Tong Univ, Key Lab Sci & Engn Comp, Dept Math, 800 Dongchuan Rd, Shanghai 200240, Peoples R China
来源：
ARS MATHEMATICA CONTEMPORANEA | 2017年 / 13卷 / 01期
基金：
中国国家自然科学基金;
关键词：
Erdos-Sos Conjecture; tree; maximum degree; CONSTRUCTING TREES;
D O I：
暂无
中图分类号：
O29 [应用数学];
学科分类号：
070104 ;
摘要：
The Erdos-Sos Conjecture states that if G is a simple graph of order n with average degree more than k - 2; then G contains every tree of order k. In this paper, we prove that Erdos-Sos Conjecture is true for n = k + 4.
引用
收藏
页码：49 / 61
页数：13
相关论文
共 18 条
  • [1] Constructing trees in graphs with no K2,s
    Balasubramanian, Surnan
    Dobson, Edward
    [J]. JOURNAL OF GRAPH THEORY, 2007, 56 (04) : 301 - 310
  • [2] The Erdos-Sos conjecture for graphs of girth 5
    Brandt, S
    Dobson, E
    [J]. DISCRETE MATHEMATICS, 1996, 150 (1-3) : 411 - 414
  • [3] Constructing trees in graphs whose complement has no K2,s
    Dobson, E
    [J]. COMBINATORICS PROBABILITY & COMPUTING, 2002, 11 (04) : 343 - 347
  • [4] Eaton N, 2010, ARS COMBINATORIA, V95, P373
  • [5] Erdos P., 1965, THEORY GRAPHS ITS AP, P29
  • [6] The Erdos-Sos conjecture for spiders
    Fan, Genghua
    Sun, Lingli
    [J]. DISCRETE MATHEMATICS, 2007, 307 (23) : 3055 - 3062
  • [7] The Erdos-Sos conjecture for spiders of large size
    Fan, Genghua
    [J]. DISCRETE MATHEMATICS, 2013, 313 (22) : 2513 - 2517
  • [8] Gallai T., 1959, Acta Math. Acad. Sci. Hungar., V10, P337, DOI [10.1007/BF02024498, DOI 10.1007/BF02024498]
  • [9] Haxell PE, 2001, J GRAPH THEOR, V36, P121, DOI 10.1002/1097-0118(200103)36:3<121::AID-JGT1000>3.0.CO
  • [10] 2-U
12