Branching $k$-path vertex cover of forests
Abstract
We define a set $P$ to be a branching $k$-path vertex cover of an undirected forest $F$ if all leaves and isolated vertices (vertices of degree at most $1$) of $F$ belong to $P$ and every path on $k$ vertices (of length $k-1$) contains either a branching vertex (a vertex of degree at least $3$) or a vertex belonging to $P$. We define the branching $k$-path vertex cover number of an undirected forest $F$, denoted by $\psi_b(F,k)$, to be the number of vertices in the smallest branching $k$-path vertex cover of $F$. These notions for a rooted directed forest are defined similarly, with natural adjustments. We prove the lower bound $\psi_b(F,k) \geq \frac{n+3k-1}{2k}$ for undirected forests, the lower bound $\psi_b(F,k) \geq \frac{n+k}{2k}$ for rooted directed forests, and that both of them are tight.
Fields of Study & Subjects
Stochastic processes and statistical mechanics
Advanced Graph Theory Research
Computational Geometry and Mesh Generation
Publication details
- Journal / source
- Zenodo (CERN European Organization for Nuclear Research)
- Publication date
- 1 January 2026
- Language
- EN
- Document type
- Preprint