On the Minimum vertex k-path cover of trees

Abstract

Let G = (V, E) and k ≥ 2. A subset S of V is called a vertex k-path cover if every path of order k in G contains at least one vertex from 5. Minimum cardinality of a vertex k-path cover in G is denoted by φ_k(G) and called the vertex k-path cover number of G. We find the lower bound for φ_k in terms on the number of vertices and end vertices and characterize the extremal trees for this lower bound. In [2] it was shown that for any tree T with n vertices, φ_k(T) ≤ n/k. Here we characterize extremal φ_k-trees for this upper bound.