| 无$K_{1,4}$子图的图的路覆盖 |
| |
| 引用本文： | 刘明达,陈晓东,李明楚.无$K_{1,4}$子图的图的路覆盖[J].数学研究及应用,2019,39(3):315-320. |
| |
| 作者姓名： | 刘明达 陈晓东 李明楚 |
| |
| 作者单位： | 辽宁工业大学理学院, 辽宁 锦州 121001,辽宁工业大学理学院, 辽宁 锦州 121001,大连理工大学软件学院, 辽宁 大连 116024 |
| |
| 基金项目： | 辽宁省联合基金(Grant No.SY2016012). |
| |
| 摘 要： | 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 σ_(k+1)(G) ≥ n-k, then p(G) ≤ k, where σ_(k+1)(G) = min{∑v∈S d(v) : S is an independent set of G with |S| = k + 1}.
|
| 关 键 词： | 路覆盖 路覆盖数 无$K_{1 4}$子图的图 不可插入点 |
| 收稿时间： | 2018/7/17 0:00:00 |
| 修稿时间： | 2018/10/26 0:00:00 |
Path Cover in $K_{1,4}$-Free Graphs |
| |
| Mingda LIU,Xiaodong CHEN and Mingchu LI.Path Cover in $K_{1,4}$-Free Graphs[J].Journal of Mathematical Research with Applications,2019,39(3):315-320. |
| |
| Authors: | Mingda LIU Xiaodong CHEN and Mingchu LI |
| |
| Abstract: | 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\}$. |
| |
| Keywords: | path cover path cover number $K_{1 4}$-free graph non-insertable vertex |
| 本文献已被 CNKI 等数据库收录！ |
| 点击此处可从《数学研究及应用》浏览原始摘要信息 |
| 点击此处可从《数学研究及应用》下载免费的PDF全文 |
|
