论文部分内容阅读
本论文共由四章组成，其中第一章是对本论文所涉及问题的背景、进展以及所得结果的一个综述。
在第二章中，着重研究图的边数和某些k边树之间的关系。令G是一个n点的简单图，e(G)表示图G的边数，k是—个整数。Erdos和Gallai的一个经典结果是：如果e(G)>k-1/2n，那么G中存在一条长为k的路。Erdos和Sos由这个结果提出猜想：如果e(G)>k-1/2n，那么G中存在任意k边树。这个猜想至今未被解决，只有一些部分结果。在第二章中证明了以下结果：
如果e(G)>k-1/2n，那么：
(1)G中存在任意k边的3足蛛形树(蛛形树是指只有至多—个点的度大于2的树)。
(2)G中存在任意足长不超过4的k边蛛形树。
(3)G中存在任意直径不超过9的k边蛛形树。
其中结果(2)(3)推广了Wozniak的关于蛛形树的结果。
在第三章中，着重研究图的中间度和某些k边树之间的关系。1994年，Loebl猜想将Erdos—Sos猜想中平均度大于k-1的条件换成中间度至少为k(k=n/2)，结论仍成立。后来Komlos和Sos猜想这个结论对一般的k也成立。Loebl—Komlos-Sos猜想:如果图G中至少一半的点的度至少为k，那么G中存在任意k边树。解决这个猜想似乎很困难，至今只有极少的部分结果。在第三章中证明了以下结果：
如果G是n点图且至少一半的点的度至少为k，那么
(1)G中存在任意直径不超过4的树。
(2)G中存在任意直径不超过5的蛛形树。
最后在第四章，着重研究叶子数被某些参数所限制的生成树问题。Flandrin等人于2003年在中关于推广Chvatal—Erdos定理提出以下问题：任意图G是否有一个生成树，其叶子数至多为α(G)-k(G)+1(这里α(G)和k(G)分别表示图G的独立数和连通度)?
在第四章，证明了上面的问题在k(G)≤2时是成立的，并利用其中的一个结果改进了Rahman和Kaykobad在中提出的算法。