KATRENIČ , Ján

The dissociation number of a graph G is the number of vertices in a maximum size induced subgraph of G with vertex degree at most 1. A k-path vertex cover of a graph G is a subset S of vertices of G such that every path of order k in G contains at least one vertex from S. The minimum 3-path vertex cover is a dual problem to the dissociation...

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 P_k(G) the minimum cardinality of a k-path vertex cover in G. It is shown that the problem of determining P_k(G) is NP-hard for each k ≥ 2, while for trees the problem can be solved in linear time. We...