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 NameAffiliation
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
Download times: 198
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  Download reader