On the Path Sequence of a Graph

A subset S of vertices of a graph $G = (V, E)$ is called a $k$-path vertex cover if every path on $k$ vertices in $G$ contains at least one vertex from $S$. Denote by $psi_k(G)$ the minimum cardinality of a $k$-path vertex cover in $G$ and form a sequence $\psi(G) = (\psi_1 (G), \psi_2 (G), . . . , \psi_{|V|} (G))$, called the path sequence of $G$. In this paper we prove necessary and sufficient conditions for two integers to appear on fixed positions in $\psi(G)$. A complete list of all possible path sequences (with multiplicities) for small connected graphs is also given.