On the vertex k k -path cover
A subset S S of vertices of a graph G G is called a vertex k k -path cover if every path of order k k in G G contains at least one vertex from S S . Denote by ?k(G) ? k ( G ) the minimum cardinality of a vertex k k -path cover in G G . In this paper, an upper bound for ?3 ? 3 in graphs with a given average degree is presented. A lower bound for ?k ? k of regular graphs is also proven. For grids, i.e. the Cartesian products of two paths, we give an asymptotically tight bound for ?k ? k and the exact value for ?3 ? 3 .
average degree regular graphs grids k k -path vertex cover k k k k k