Spanning trees with a bounded number of leaves in a claw-free graph
Spanning trees with a bounded number of leaves in a claw-free graph
复制标题
DOI：
--
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
M. Kano;Aung Kyaw;Haruhide Matsuda;K. Ozeki;Akira Saito;T. Yamashita
中科院分区：
文献类型：
--
作者：
M. Kano;Aung Kyaw;Haruhide Matsuda;K. Ozeki;Akira Saito;T. Yamashita
对于图 H 和整数 k ≥ 2，设 σk(H) 表示 H 的 k 个独立顶点的最小度和。我们证明，如果连通无爪图 G 满足 σk+1(G) ≥ |G| − k，则 G 有一棵最多有 k 个叶子的生成树。我们还证明了绑定|G| − k 是尖锐的并讨论所需生成树的最大度。
For a graph H and an integer k ≥ 2, let σk(H) denote the minimum degree sum of k independent vertices of H. We prove that if a connected claw-free graph G satisfies σk+1(G) ≥ |G| − k, then G has a spanning tree with at most k leaves. We also show that the bound |G| − k is sharp and discuss the maximum degree of the required spanning trees.