Minimum path cover in quasi-claw-free graphs (Q779733)

A collection \(\mathcal{P}\) of vertex disjoint paths of a graph \(G\) is called a path cover of \(G\) if any vertex of \(G\) belongs to some path in \(\mathcal{P}\). The path cover number of \(G\), denoted by \(p(G)\), is defined to be \(\min \{|\mathcal{P}| : \mathcal{P} \mbox{ is a path cover of } \)G\(\}\). Let \(N(v)\) (\(N[v]\)) denote the open (closed) neighborhood of a vertex \(v\). A graph \(G\) is called quasi-claw-free if the following condition holds. For any two vertices \(x\) and \(y\) at distance 2 in \(G\), there exists a vertex \(u\) such that \(u \in N(x) \cap N(y)\) and \(N(u) \subseteq N[x] \cup N[y]\). Let \(\sigma_{k+1}(G)\) denote the minimum degree sum of an independent set with \(k+1\) vertices in \(G\). The main result of this paper states as follows. Let \(G\) be a quasi-claw-free graph on \(n\) vertices. Then \(p(G) \leq k\) if \(\sigma_{k+1}(G) \geq n-k\) for some positive integer \(k\).