Spanning Trees with Few Leaves in Almost Claw-Free Graphs

DOI：10.3770/j.issn:2095-2651.2016.04.007

 作者 单位 陈晓东 辽宁工业大学理学院, 辽宁 锦州 121001 李明楚 大连理工大学软件学院, 辽宁 116024 徐美进 辽宁工业大学理学院, 辽宁 锦州 121001

叶子数目不大于3的生成树称为3-末端生成树.本文证明若图$G$为一个$k(k\ge 2)$连通的阶数为$n$的几乎无爪图且$\sigma_{k+3}(G)\ge n+2k-2$, 则该图含有3-末端生成树,其中$\sigma_k(G)=\min\{\sum_{u\in S}{\rm deg}(v)$: $S$为含有$k$个独立点的集合$\}$.

A spanning tree with no more than 3 leaves is called a spanning 3-ended tree. In this paper, we prove that if $G$ is a $k$-connected ($k\geq 2$) almost claw-free graph of order $n$ and $\sigma_{k+3}(G)\geq {n+k+2}$, then $G$ contains a spanning 3-ended tree, where $\sigma_k(G)=\min\{\sum_{v\in S}{\rm deg}(v):S$ is an independent set of $G$ with $|S|=k\}$.