Small hitting sets for longest paths and cycles

Motivated by an old question of Gallai (1966) on the intersection of longest paths in a graph and the famous conjectures of Lovász (1969) and Thomassen (1978) on the maximum length of paths and cycles in vertex-transitive graphs, we present improved bounds for the parameters l p t ( G ) \mathrm {lpt}(G) and l c t ( G ) \mathrm {lct}(G) , defined as the minimum size of a set of vertices in a graph G G hitting all longest paths (cycles, respectively). First, we show that every connected graph G G on n n vertices satisfies l p t ( G ) ≤ 8 n \mathrm {lpt}(G)\le \sqrt {8n} , and l c t ( G ) ≤ 8 n \mathrm {lct}(G)\le \sqrt {8n} if G G is additionally 2 2 -connected. This improves a sequence of earlier bounds for these problems, with the previous state of the art being O ( n 2 / 3 ) O(n^{2/3}) . Second, we show that every connected graph G G satisfies