A variation of a conjecture due to Erdös and Sós
A variation of a conjecture due to Erdös and Sós
复制标题
DOI：
10.1007/s10114-009-7260-2
复制
发表时间：
2009-04
期刊：
影响因子：
--
通讯作者：
Jianhua Yin;Jiongsheng Li
中科院分区：
文献类型：
--
作者：
Jianhua Yin;Jiongsheng Li
Erdös和Sós在1963年推测，每一个边号为(G) >½（k−1）n的graphGonnvertices包含每一个treeTwithkedges作为子图。在本文中，我们考虑了上述猜想的一种变体，即在≥9/2k2+ 37/2k+14且每个图的顶点为(G) > 1 /2 (k−1)n的情况下，我们证明了存在一个图G的顶点具有与G相同的度序列，并且包含每一个树形图作为子图。
Erdös and Sós conjectured in 1963 that every graphGonnvertices with edge numbere(G) > ½ (k− 1)ncontains every treeTwithkedges as a subgraph. In this paper, we consider a variation of the above conjecture, that is, forn≥ 9/2k2+ 37/2k+14 and every graphGonnvertices withe(G) > ½ (k− 1)n, we prove that there exists a graphG′ onnvertices having the same degree sequence asGand containing every treeTwithkedges as a subgraph.