On path sequences of graphs

Abstract

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),\dots ,{\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.

10 pages, 3 tables; submitted to Schedae Informaticae

References in corpus (1)

• Minimum k-path vertex cover