Branching $k$-path vertex cover of forests
By: Mikhail Makarov
Potential Business Impact:
Finds smallest groups to cover all paths.
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 adjustments. We prove the lower bound $ψ_b(F,k) \geq \frac{n+3k-1}{2k}$ for undirected forests, the lower bound $ψ_b(F,k) \geq \frac{n+k}{2k}$ for rooted directed forests, and that both of them are tight.
Similar Papers
Spanning Trees with a Small Vertex Cover: the Complexity on Specific Graph Classes
Data Structures and Algorithms
Finds special tree structures in computer networks.
On graphs coverable by chubby shortest paths
Combinatorics
Finds patterns in networks for better computer problem-solving.
Lower Bounds on Tree Covers
Data Structures and Algorithms
Makes maps easier to use with fewer roads.