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 条

[31] Application of upper and lower bounds for the domination number to Vizing's conjecture [J].

Clark, WE ;

Ismail, MEH ;

Suen, S .

ARS COMBINATORIA, 2003, 69 :97-108

[32] Towards generalizing MacDougall's conjecture on vertex-magic total labelings [J].

Gibson, Keith ;

Golkaramnay, Artmiz ;

McQuillan, Dan .

DISCRETE MATHEMATICS, 2020, 343 (12)

[33] Gallai's path decomposition conjecture for triangle-free planar graphs [J].

Botler, F. ;

Jimenez, A. ;

Sambinelli, M. .

DISCRETE MATHEMATICS, 2019, 342 (05) :1403-1414

[34] Graph decomposition is NP-complete: A complete proof of Holyer's conjecture [J].

Dor, D ;

Tarsi, M .

SIAM JOURNAL ON COMPUTING, 1997, 26 (04) :1166-1187

[35] PROOF OF SLATER'S CONJECTURE ON k-CRITICAL n-CONNECTED GRAPHS [J].

苏健基 .

Science Bulletin, 1988, (20) :1675-1678

[36] Two short proofs of the bounded case of SB Rao's degree sequence conjecture [J].

Sivaraman, Vaidy .

DISCRETE MATHEMATICS, 2013, 313 (13) :1500-1501

[37] A semigroup proof of the bounded degree case of SB Rao's Conjecture on degree sequences and a bipartite analogue [J].

Altomare, Christian Joseph .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 2012, 102 (03) :756-759

[38] A Havel-Hakimi type procedure and a sufficient condition for a sequence to be potentially S r,s -graphic [J].

Yin, Jian-Hua .

CZECHOSLOVAK MATHEMATICAL JOURNAL, 2012, 62 (03) :863-867

[39] Moderate deviations of triangle counts in sparse Erdős-Rényi random graphs G(n, m) and G(n, p) [J].

Alvarado, Jose D. ;

de Oliveira, Leonardo Goncalves ;

Griffiths, Simon .

PROBABILITY THEORY AND RELATED FIELDS, 2025, 191 (3-4) :779-851

[40] TheErds-SósConjectureforGraphsWhoseComplementsContainNoC4 [J].

Jianhua Yin Jiongsheng Li Department of Applied MathematicsCollege of Information Science and TechnologyHainan UniversityHaikou ChinaEmailyinjhustcedu Department of MathematicsUniversity of Science and Technology of ChinaHefei China .

Acta Mathematicae Applicatae Sinica(English Series), 2004, (03) :43-46

← 1 2 3 4 5 →