{"id":"arxiv/2601.02685","url":"https://arxiv.org/abs/2601.02685","tags":["math.CO","cs.DM"],"score":0,"title":"Branching $k$-path vertex cover of forests","domain":"math.CO","source":"arxiv","authors":["Mikhail Makarov"],"reviews":0,"subject":"math.CO","summary":"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 $ψ_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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-01-06","reactions":{}}