刘明达,陈晓东,李明楚.无$K_{1,4}$子图的图的路覆盖[J].数学研究及应用,2019,39(3):315~320
无$K_{1,4}$子图的图的路覆盖
Path Cover in $K_{1,4}$-Free Graphs
投稿时间:2018-07-17  修订日期:2018-10-26
DOI:10.3770/j.issn:2095-2651.2019.03.011
中文关键词:  路覆盖  路覆盖数  无$K_{1,4}$子图的图  不可插入点
英文关键词:path cover  path cover number  $K_{1,4}$-free graph  non-insertable vertex
基金项目:辽宁省联合基金(Grant No.SY2016012).
作者单位
刘明达 辽宁工业大学理学院, 辽宁 锦州 121001 
陈晓东 辽宁工业大学理学院, 辽宁 锦州 121001 
李明楚 大连理工大学软件学院, 辽宁 大连 116024 
摘要点击次数: 906
全文下载次数: 779
中文摘要:
      图$G$的路覆盖为该图的一个由点不交的路而构成的$G$的生成子图; 路覆盖数, 记为$p(G)$, 表示$G$的所有路覆盖中含有路的条数最少的路覆盖所含有的路的条数.本篇论文证明了若图$G$为一个阶数为$n$,无$K_{1,4}$子图的图,且$\delta_{k+1}(G)\ge n-k$,则图$G$的路覆盖数至多为$k$.
英文摘要:
      For a graph $G,$ a path cover is a set of vertex disjoint paths covering all the vertices of $G$, and a path cover number of $G,$ denoted by $p(G),$ is the minimum number of paths in a path cover among all the path covers of $G.$ In this paper, we prove that if $G$ is a $K_{1,4}$-free graph of order $n$ and $\sigma_{k+1}(G)\geq {n-k}$, then $p(G)\leq k$, where $\sigma_{k+1}(G)=\min\{\sum_{v\in S}{\rm d}(v):S$ is an independent set of $G$ with $|S|=k+1\}$.
查看全文  查看/发表评论  下载PDF阅读器