The k-path vertex cover: general bounds and chordal graphs

Abstract

For an integer $k\ge 3$, a $k$-path vertex cover of a graph $G=(V,E)$ is a set $T\subseteq V$ that shares a vertex with every path subgraph of order $k$ in $G$. The minimum cardinality of a $k$-path vertex cover is denoted by ${\psi }_k(G)$. We give estimates -- mostly upper bounds -- on ${\psi }_k(G)$ in terms of various parameters, including vertex degrees and the number of vertices and edges. The problem is also considered on chordal graphs and planar graphs.

21 pages