Transversals of Longest Paths and Cycles
Transversals of Longest Paths and Cycles
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 …