On the -path vertex cover of some graph products

A subset S of vertices of a graph G is called a k -path vertex cover if every path of order k in G contains at least one vertex from S . Denote by ψ k ( G ) the minimum cardinality of a k -path vertex cover in G . In this paper, improved lower and upper bounds for ψ k of the Cartesian and the strong product of paths are derived. It is shown that for ψ 3 those bounds are tight. For the lexicographic product bounds are presented for ψ k , moreover ψ 2 and ψ 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.