The k-path vertex cover in Cartesian product graphs and complete bipartite graphs

摘要

For a graph G and a positive integer k, a subset S of vertices of G is called a k-path vertex cover if S intersects all paths of order k in G. The cardinality of a minimum k-path vertex cover is denoted by ψk(G), and called the k-path vertex cover number of G. In this paper, we study some Cartesian product graphs and give several estimations and the exact values of ψk(G).