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 NameAffiliationAddress
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: 102
Download times: 
      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\}$.
  View/Add Comment  Download reader