关于至多有3个叶子的支撑树的存在性研究

Research on the Existence of Spanning Trees with at Most Three Leaves

摘要: 在2009年，Kyaw在[Discrete Mathematics, 309, 6146~6148]中证明了对于阶数为n的连通图G且图G中不包含同构于 的导出子图，若图G中任意4个独立顶点的度和至少为 ，则图G中存在至多3个叶子的支撑树。在这篇文章中我们考虑了邻域并条件，得到了一个类似的结果，即对于阶数为n的连通图G且图G中不包含同构于 的导出子图，若图G中任意4个独立顶点的邻域并的基数至少为 ，则图G中存在至多3个叶子的支撑树，并且得到的下界是最好可能的。

Abstract: In 2009, Kyaw in [Discrete Mathematics, 309, 6146~6148] proved that every connected graph G of order n that contains no induced subgraph isomorphic to has a spanning tree with at most 3 leaves if the degree sum of any 4 independent vertices in G is at least . In this paper, we con-sider the neighborhood union condition and obtain a similar result. We show that every connected graph G of order n that contains no induced subgraph isomorphic to has a spanning tree with at most 3 leaves if the cardinality of the neighborhood union of any 4 independent vertices in G isat least . Moreover, the lower bound is best possible.