Transversals of Longest Paths and Cycles
Dieter Rautenbach, Jean‐Sébastien Sereni · SIAM Journal on Discrete Mathematics · 2014
Let $G$ be a graph of order $n$. Let $\mathrm{lpt}(G)$ be the minimum cardinality of a set $X$ of vertices of $G$ such that $X$ intersects every longest path of $G$, and define $\mathrm{lct}(G)$ analogously for cycles instead of paths. We prove that $\mathrm{lpt}(G)\leqslant \lceil\frac{n}{4}-\frac{n^{2/3}}{90}\rceil$ if $G$ is connected, and $\mathrm{lct}(G)\leqslant \lceil\frac{n}{3}-\frac{n^{2/3}}{36}\rceil$ if $G$ is $2$-connected. Our bound on $\mathrm{lct}(G)$ improves an earlier result of Thomassen. Furthermore, we prove upper bounds on $\mathrm{lpt}(G)$ for planar graphs and graphs of bounded tree-width.