On the k-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 kin G contains at least one vertex from S. Denote by psi(k)(G) the minimum cardinality of a k-path vertex cover in G. In this paper, improved lower and upper bounds for psi(k) of the Cartesian and the strong product of paths are derived. It is shown that for psi(3) those bounds are tight. For the lexicographic product bounds are presented for psi(k), moreover psi(2) and psi(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. (C) 2012 Elsevier B.V. All rights reserved.