Path Cover in $K_{1,4}$-Free Graphs |
Received:July 17, 2018 Revised:October 26, 2018 |
Key Words:
path cover path cover number $K_{1,4}$-free graph non-insertable vertex
|
Fund Project:Supported by the Joint Fund of Liaoning Provincial Natural Science Foundation (Grant No.SY2016012). |
|
Hits: 1044 |
Download times: 850 |
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\}$. |
Citation: |
DOI:10.3770/j.issn:2095-2651.2019.03.011 |
View Full Text View/Add Comment |
|
|
|