On the kk-path vertex cover of some graph products

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. In this paper, improved lower and upper bounds for ψkψk of the Cartesian and the strong product of paths are derived. It is shown that for ψ3ψ3 those bounds are tight. For the lexicographic product bounds are presented for ψkψk, moreover ψ2ψ2 and ψ3ψ3 are exactly determined for the lexicographic product of two arbitrary graphs. As a consequence the independence and the dissociation number of the lexicographic product are given.