Minimum kk-path vertex cover

A subset SS of vertices of a graph GG is called a kk-path vertex 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 kk-path vertex cover in GG. It is shown that the problem of determining ψk(G)ψk(G) is NP-hard for each k≥2k≥2, while for trees the problem can be solved in linear time. We investigate upper bounds on the value of ψk(G)ψk(G) and provide several estimations and exact values of ψk(G)ψk(G). We also prove that ψ3(G)≤(2n+m)/6ψ3(G)≤(2n+m)/6, for every graph GG with nn vertices and mm edges.