Path Cover in $K_{1,4}$-Free Graphs
Received:July 17, 2018  Revised:October 26, 2018
Key Word: path cover   path cover number   $K_{1,4}$-free graph   non-insertable vertex
Fund ProjectL:Supported by the Joint Fund of Liaoning Provincial Natural Science Foundation (Grant No.SY2016012).
 Author Name Affiliation Mingda LIU College of Science, Liaoning University of Technology, Liaoning 121001, P. R. China Xiaodong CHEN College of Science, Liaoning University of Technology, Liaoning 121001, P. R. China Mingchu LI School of Softsware, Dalian University of Technology, Liaoning 116024, P. R. China
Hits: 216
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\}$.