Path cover in $K_{1,4}$-free graphs
Received:July 17, 2018  Revised:December 12, 2018
Key Word: path cover   path cover number   $K_{1,4}$-free graph   non-insertable vertex
Fund ProjectL:Supported by the National Natural Science Foundation of China, Tian Yuan Special Foundation (Grant No.\,11426125); The Joint Fund of Liaoning Province Natural Science Foundation (Grant No.\,SY2016012); Educational Commission of Liaoning Province (Grant No.\,L2014239).
 Author Name Affiliation Address Mingda Liu Science of Colledge, Liaoning University of Technology 辽宁省锦州市古塔区士英街169号 Xiaodong Chen Science of Colledge, Liaoning University of Technology 辽宁省锦州市古塔区士英街169号 Mingchu Li Science of Colledge, Dalian University of Technology
Hits: 40
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 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\}$.