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 ]
机构
关键词
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 条
[41]   About chromatic uniqueness of complete tripartite graph K(s, s - 1, s - k), where k >= 1 and s - k >= 2 [J].
Gein, P. A. .
SIBERIAN ELECTRONIC MATHEMATICAL REPORTS-SIBIRSKIE ELEKTRONNYE MATEMATICHESKIE IZVESTIYA, 2016, 13 :331-337
[42]   A variation of the classical Lovasz's (g, f)-parity factor theorem in degree sequences [J].
Guo, Ji-Yun ;
Yin, Jian-Hua .
UTILITAS MATHEMATICA, 2015, 97 :225-231
[43]   A Variation of the ErdAs-Ss Conjecture in Bipartite Graphs [J].
Yuan, Long-Tu ;
Zhang, Xiao-Dong .
GRAPHS AND COMBINATORICS, 2017, 33 (02) :503-526
[44]   On the complexity of recognizing S-composite and S-prime graphs [J].
Hellmuth, Marc .
DISCRETE APPLIED MATHEMATICS, 2013, 161 (7-8) :1006-1013
[45]   The differential on operator S(Γ) [J].
Castro, Jair ;
Basilio, Ludwin A. ;
Reyna, Gerardo ;
Rosario, Omar .
MATHEMATICAL BIOSCIENCES AND ENGINEERING, 2023, 20 (07) :11568-11584
[46]   A variant of Niessen's problem on degree sequences of graphs [J].
Guo, Ji-Yun ;
Yin, Jian-Hua .
DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE, 2014, 16 (01) :287-292
[47]   Graph partition into K3s and K4s [J].
Zhang B. ;
Yan J. .
Journal of Applied Mathematics and Computing, 2010, 34 (1-2) :273-285
[48]   An extremal problem on potentially Kr,s-graphic sequences [J].
Yin, JH ;
Li, JS .
DISCRETE MATHEMATICS, 2003, 260 (1-3) :295-305
[49]   On Wiman's theorem for graphs [J].
Mednykh, Alexander ;
Mednykh, Ilya .
DISCRETE MATHEMATICS, 2015, 338 (10) :1793-1800
[50]   On S-Zariski topology [J].
Yildiz, Eda ;
Ersoy, Bayram Ali ;
Tekir, Unsal ;
Koc, Suat .
COMMUNICATIONS IN ALGEBRA, 2021, 49 (03) :1212-1224