Improved upper bounds on longest-path and maximal subdivision transversals

Henry Kierstead, Eric Ren

Let $G$ be a connected graph on $n$ vertices. The Gallai number $Gal(G)$ of $G$ is the size of the smallest set of vertices that meets every maximum path in $G$. Grünbaum construct…