陈晓东,李明楚,徐美进.几乎无爪图的叶子数较少的生成树[J].数学研究及应用,2016,36(4):450~456
几乎无爪图的叶子数较少的生成树
Spanning Trees with Few Leaves in Almost Claw-Free Graphs
投稿时间:2015-10-20  修订日期:2016-04-15
DOI:10.3770/j.issn:2095-2651.2016.04.007
中文关键词:  3-末端生成树  几乎无爪图  可插入点
英文关键词:spanning 3-ended tree  almost claw-free graph  insertible vertex, non-insertible vertex
基金项目:国家自然科学基金数学天元基金项目(Grant No.11426125),辽宁省教育厅(Grant No.L2014239).
作者单位
陈晓东 辽宁工业大学理学院, 辽宁 锦州 121001 
李明楚 大连理工大学软件学院, 辽宁 116024 
徐美进 辽宁工业大学理学院, 辽宁 锦州 121001 
摘要点击次数: 2660
全文下载次数: 1810
中文摘要:
      叶子数目不大于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\}$.
查看全文  查看/发表评论  下载PDF阅读器