无爪图中分支顶点与叶子顶点总数不超过6的生成树
Spanning Trees with at Most Six Branch Vertices and Leaves in Total ofClaw-Free Graphs
DOI: 10.12677/AAM.2026.159377, PDF,   
作者: 张跃：辽宁师范大学数学学院，辽宁 大连
关键词: 生成树；无爪图；叶子；分支顶点；Spanning Trees； Claw-Free； Leaves； Branch Vertices
摘要: 树的叶子是度数为1的顶点，树的分支顶点是度数至少为3的顶点。Hanh提出猜想：对任意非负整 数k，满足σ2k+3(G)≥n-2的n阶连通无爪图必存在生成树T，满足|B(T)|+|L(T)|≤2k+3，并 且证明了当k=1时该猜想成立。本文证明：任意n阶连通无爪图G，若满足σ6(G)≥n-2，则G中 存在一棵生成树，其叶子与分支顶点的总数不超过6。并且该度和条件是最优的。
Abstract: A leaf of a tree is a vertex of degree one and a branch vertex of a tree is a vertex of degree at least three. Hanh conjectured that for any nonnegative integer k, every connected claw-free graph of order n with σ2k+3(G) ≥ n − 2 contains a spanning tree T with |B(T )| + |L(T )| ≤ 2k + 3 and proved that the conjecture holds when k = 1. In this paper, we show that every n-vertex connected claw-free graph G with σ6(G) ≥ n − 2 contains a spanning tree with at most six leaves and branch vertices in total. Moreover, the degree sum condition is best possible.
文章引用：张跃. 无爪图中分支顶点与叶子顶点总数不超过6的生成树[J]. 应用数学进展, 2026, 15(9): 101-112. https://doi.org/10.12677/AAM.2026.159377

参考文献

[1] Maezawa, S., Matsubara, R. and Matsuda, H. (2019) Degree Conditions for Graphs to Have Spanning Trees with Few Branch Vertices and Leaves. Graphs and Combinatorics, 35, 231-238. [Google Scholar] [CrossRef] 
[2] Kyaw, A. (2009) Spanning Trees with at Most 3 Leaves in k1,4-Free Graphs. Discrete Mathe- matics, 309, 6146-6148. [Google Scholar] [CrossRef] 
[3] Kyaw, A. (2011) Spanning Trees with at Most k Leaves in k1,4-Free Graphs. Discrete Mathe- matics, 311, 2135-2142. [Google Scholar] [CrossRef] 
[4] Kano, M., Kyaw, A., Matsuda, H., Ozeki, K., Saito, A. and Yamashita, T. (2012) Spanning Trees with a Bounded Number of Leaves in a Claw-Free Graph. Ars Combinatoria, 103, 137- 154.
[5] Gould, R.J. and Shull, W. (2020) On Spanning Trees with Few Branch Vertices. Discrete Mathematics, 343, Article ID: 111581. [Google Scholar] [CrossRef] 
[6] Ha, P.H. (2025) Spanning Trees of k1,4-Free Graphs with a Bounded Number of Leaves and Branch Vertices. Acta Mathematica Vietnamica, 50, 263-271. [Google Scholar] [CrossRef] 
[7] Ha, P.H. and Trang, N.H. (2024) Spanning Trees with at Most 5 Leaves and Branch Vertices in Total of k1,5-Free Graphs. Taiwanese Journal of Mathematics, 28, 847-855. [Google Scholar] [CrossRef] 
[8] Hanh, D.D. (2022) Degree Conditions for Claw-Free Graphs to Have Spanning Trees with at Most Five Branch Vertices and Leaves in Total. Studia Scientiarum Mathematicarum Hungar- ica, 59, 58-66. [Google Scholar] [CrossRef] 

为你推荐