几乎无爪图的叶子数较少的生成树

Spanning Trees with Few Leaves in Almost Claw-Free Graphs

中文关键词:  3-末端生成树  几乎无爪图  可插入点

英文关键词:spanning 3-ended tree  almost claw-free graph  insertible vertex, non-insertible vertex

中文摘要:

      叶子数目不大于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\}$.