Sublinear Longest Path Transversals

Abstract

We show that connected graphs admit sublinear longest path transversals. This improves an earlier result of Rautenbach and Sereni and is related to the fifty-year-old question of whether connected graphs admit longest path transversals of constant size. The same technique allows us to show that $2$-connected graphs admit sublinear longest cycle transversals.

A previous version of this arXiv post has been split into two parts; this is the first of the two parts

Cited by in corpus (2)

• Non-empty intersection of longest paths in $H$-free graphs
• Longest cycles in vertex-transitive and highly connected graphs