The Erdos-Sos Conjecture for trees of diameter four

被引：34

作者：

McLennan, A ^{[1
]}

机构：

[1] Univ Minnesota, Dept Econ, Minneapolis, MN 55455 USA

来源：

JOURNAL OF GRAPH THEORY | 2005年 / 49卷 / 04期

关键词：

Erdos-Sos Conjecture; extremal graph theory;

D O I：

10.1002/jgt.20083

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

The Erdos-Sos Conjecture is that a finite graph G with average degree greater than k - 2 contains every tree with k vertices. Theorem 1 is a special case: every k-vertex tree of diameter four can be embedded in G. A more technical result, Theorem 2, is obtained by extending the main ideas in the proof of Theorem 1. (C) 2005 Wiley Periodicals, Inc.

引用

页码：291 / 301

页数：11

共 11 条

[1]

[Anonymous], NEW TRENDS DISCRETE

[2] The Erdos-Sos conjecture for graphs of girth 5 [J].

Brandt, S ;

Dobson, E .

DISCRETE MATHEMATICS, 1996, 150 (1-3) :411-414

[3]

Burr S.A., 1976, Utilitas Mathematica, V9, P247

[4]

Chung F., 1999, ERDOS GRAPHS HIS LEG

[5]

Erd P., 1965, Theory of Graphs and Appl, P29

[6]

Erdos P., 1959, Acta Math. Acad. Sci. Hungar., V10, P337, DOI DOI 10.1007/BF02024498

[7] The Erdos-Sos conjecture for graphs without C-4 [J].

Sacle, JF ;

Wozniak, M .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 1997, 70 (02) :367-372

[8] ASYMPTOTIC SOLUTION FOR A NEW CLASS OF FORBIDDEN R-GRAPHS [J].

SIDORENKO, AF .

COMBINATORICA, 1989, 9 (02) :207-215

[9]

Wang M., 2000, ARS COMBINATORIA, V55, P123

[10]

Wozniak M, 1996, J GRAPH THEOR, V21, P229

← 1 2 →