A Variation of a Conjecture Due to Erds and Sós

被引：0

作者：

Jian Hua YINDepartment of Mathematics School of Information Science and TechnologyHainan University Haikou PR ChinaJiong Sheng LIDepartment of Mathematics University of Science and Technology of ChinaHefei PR China ^{[570228
,230026
]}

机构：

来源：

ActaMathematicaSinica(EnglishSeries) | 2009年 / 25卷 / 05期

关键词：

graph; degree sequence; Erdos-Sos conjecture;

D O I：

暂无

中图分类号：

O157.5 [图论];

学科分类号：

070104 ;

摘要：

<正> Erdos and Sos conjectured in 1963 that every graph G on n vertices with edge numbere（G） > 1/2（k - 1）n contains every tree T with k edges as a subgraph.In this paper,we consider avariation of the above conjecture,that is,for n > 9/2k2 + 37/2k + 14 and every graph G on n vertices withe（G） > 1/2 （k-1）n,we prove that there exists a graph G' on n vertices having the same degree sequenceas G and containing every tree T with k edges as a subgraph.

引用

页码：795 / 802

页数：8

共 50 条

[21] On a conjecture that strengthens Kundu's k-factor theorem [J].

Shook, James M. .

JOURNAL OF GRAPH THEORY, 2025, 108 (03) :463-491

[22] Graph minors. XX. Wagner's conjecture [J].

Robertson, N ;

Seymour, PD .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 2004, 92 (02) :325-357

[23] Frankl's conjecture and lattices derived from reduced semigroups [J].

Joshi, Vinayak .

JOURNAL OF THE RAMANUJAN MATHEMATICAL SOCIETY, 2021, 36 (04) :301-307

[24] A proof of Cunningham's conjecture on restricted subgraphs and jump systems [J].

Kobayashi, Yusuke ;

Szabo, Jacint ;

Takazawa, Kenjiro .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 2012, 102 (04) :948-966

[25] A proof of Alon's second eigenvalue conjecture and related problems [J].

Friedman, Joel .

MEMOIRS OF THE AMERICAN MATHEMATICAL SOCIETY, 2008, 195 (910) :1-+

[26] The Erdocombining double acute accents-Sós conjecture for graphs whose complements contain No C4 [J].

Yin J.-H. ;

Li J.-S. .

Acta Mathematicae Applicatae Sinica, 2004, 20 (3) :397-400

[27] A step towards the strong version of Havel's three color conjecture [J].

Borodin, O. V. ;

Glebov, A. N. ;

Jensen, T. R. .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 2012, 102 (06) :1295-1320

[28] On the deductive strength of the Erdős–Dushnik–Miller theorem and two order-theoretic principles [J].

Eleftherios Tachtsis .

Monatshefte für Mathematik, 2024, 203 :677-693

[29] Gallai's path decomposition conjecture for graphs with treewidth at most 3 [J].

Botler, Fabio ;

Sambinelli, Maycon ;

Coelho, Rafael S. ;

Lee, Orlando .

JOURNAL OF GRAPH THEORY, 2020, 93 (03) :328-349

[30] A strengthening of Erdos-Gallai Theorem and proof of Woodall's conjecture [J].

Li, Binlong ;

Ning, Bo .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 2021, 146 :76-95

← 1 2 3 4 5 →