On the vertex kk-path cover

A subset SS of vertices of a graph GG is called a vertex kk-path cover if every path of order kk in GG contains at least one vertex from SS. Denote by ψk(G)ψk(G) the minimum cardinality of a vertex kk-path cover in GG. In this paper, an upper bound for ψ3ψ3 in graphs with a given average degree is presented. A lower bound for ψkψk of regular graphs is also proven. For grids, i.e. the Cartesian products of two paths, we give an asymptotically tight bound for ψkψk and the exact value for ψ3ψ3.