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 条

[11] Hadwiger's Conjecture is Decidable [J].

Kawarabayashi, Ken-ichi ;

Reed, Bruce .

STOC'09: PROCEEDINGS OF THE 2009 ACM SYMPOSIUM ON THEORY OF COMPUTING, 2009, :445-454

[12] The preservation property of Brouwer's conjecture [J].

Lin, Zhen ;

Wang, Ke .

DISCRETE MATHEMATICS LETTERS, 2025, 15 :39-45

[13] A NOTE ON VIZING'S GENERALIZED CONJECTURE [J].

Blidia, Mostafa ;

Chellali, Mustapha .

OPUSCULA MATHEMATICA, 2007, 27 (02) :181-185

[14] The principal Erd δs-Gallai differences of a degree sequence [J].

Barrus, Michael D. .

DISCRETE MATHEMATICS, 2022, 345 (04)

[15] Towards Gallai's path decomposition conjecture [J].

Botler, Fabio ;

Sambinelli, Maycon .

JOURNAL OF GRAPH THEORY, 2021, 97 (01) :161-184

[16] On the full Brouwer's Laplacian spectrum conjecture [J].

Li, Wen-Jun ;

Guo, Ji-Ming .

DISCRETE MATHEMATICS, 2022, 345 (12)

[17] On possible counterexamples to Negami's planar cover conjecture [J].

Hlineny, P ;

Thomas, R .

JOURNAL OF GRAPH THEORY, 2004, 46 (03) :183-206

[18] On Frank's conjecture on k-connected orientations [J].

de Gevigney, Olivier Durand .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 2020, 141 :105-114

[19] Gallai's Conjecture For Graphs of Girth at Least Four [J].

Harding, Peter ;

McGuinness, Sean .

JOURNAL OF GRAPH THEORY, 2014, 75 (03) :256-274

[20] Subword Complexes and Kalai's Conjecture on Reconstruction of Spheres [J].

Ceballos, Cesar ;

Doolittle, Joseph .

DISCRETE & COMPUTATIONAL GEOMETRY, 2025, 74 (01) :23-48

← 1 2 3 4 5 →