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 <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="normal l normal p normal t left-parenthesis upper G right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi mathvariant="normal">l</mml:mi> <mml:mi mathvariant="normal">p</mml:mi> <mml:mi mathvariant="normal">t</mml:mi> </mml:mrow> <mml:mo stretchy="false">(</mml:mo> <mml:mi>G</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">\mathrm {lpt}(G)</mml:annotation> </mml:semantics> </mml:math> </inline-formula> and <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="normal l normal c normal t left-parenthesis upper G right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi mathvariant="normal">l</mml:mi> <mml:mi mathvariant="normal">c</mml:mi> <mml:mi mathvariant="normal">t</mml:mi> </mml:mrow> <mml:mo stretchy="false">(</mml:mo> <mml:mi>G</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">\mathrm {lct}(G)</mml:annotation> </mml:semantics> </mml:math> </inline-formula> , defined as the minimum size of a set of vertices in a graph <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper G"> <mml:semantics> <mml:mi>G</mml:mi> <mml:annotation encoding="application/x-tex">G</mml:annotation> </mml:semantics> </mml:math> </inline-formula> hitting all longest paths (cycles, respectively). First, we show that every connected graph <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper G"> <mml:semantics> <mml:mi>G</mml:mi> <mml:annotation encoding="application/x-tex">G</mml:annotation> </mml:semantics> </mml:math> </inline-formula> on <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="n"> <mml:semantics> <mml:mi>n</mml:mi> <mml:annotation encoding="application/x-tex">n</mml:annotation> </mml:semantics> </mml:math> </inline-formula> vertices satisfies <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="normal l normal p normal t left-parenthesis upper G right-parenthesis less-than-or-equal-to StartRoot 8 n EndRoot"> <mml:semantics> <mml:mrow> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi mathvariant="normal">l</mml:mi> <mml:mi mathvariant="normal">p</mml:mi> <mml:mi mathvariant="normal">t</mml:mi> </mml:mrow> <mml:mo stretchy="false">(</mml:mo> <mml:mi>G</mml:mi> <mml:mo stretchy="false">)</mml:mo> <mml:mo> ≤ </mml:mo> <mml:msqrt> <mml:mn>8</mml:mn> <mml:mi>n</mml:mi> </mml:msqrt> </mml:mrow> <mml:annotation encoding="application/x-tex">\mathrm {lpt}(G)\le \sqrt {8n}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> , and <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="normal l normal c normal t left-parenthesis upper G right-parenthesis less-than-or-equal-to StartRoot 8 n EndRoot"> <mml:semantics> <mml:mrow> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi mathvariant="normal">l</mml:mi> <mml:mi mathvariant="normal">c</mml:mi> <mml:mi mathvariant="normal">t</mml:mi> </mml:mrow> <mml:mo stretchy="false">(</mml:mo> <mml:mi>G</mml:mi> <mml:mo stretchy="false">)</mml:mo> <mml:mo> ≤ </mml:mo> <mml:msqrt> <mml:mn>8</mml:mn> <mml:mi>n</mml:mi> </mml:msqrt> </mml:mrow> <mml:annotation encoding="application/x-tex">\mathrm {lct}(G)\le \sqrt {8n}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> if <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper G"> <mml:semantics> <mml:mi>G</mml:mi> <mml:annotation encoding="application/x-tex">G</mml:annotation> </mml:semantics> </mml:math> </inline-formula> is additionally <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="2"> <mml:semantics> <mml:mn>2</mml:mn> <mml:annotation encoding="application/x-tex">2</mml:annotation> </mml:semantics> </mml:math> </inline-formula> -connected. This improves a sequence of earlier bounds for these problems, with the previous state of the art being <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper O left-parenthesis n Superscript 2 slash 3 Baseline right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:msup> <mml:mi>n</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mn>2</mml:mn> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo>/</mml:mo> </mml:mrow> <mml:mn>3</mml:mn> </mml:mrow> </mml:msup> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">O(n^{2/3})</mml:annotation> </mml:semantics> </mml:math> </inline-formula> . Second, we show that every connected graph <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper G"> <mml:semantics> <mml:mi>G</mml:mi> <mml:annotation encoding="application/x-tex">G</mml:annotation> </mml:semantics> </mml:math> </inline-formula> satisfies <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="normal l normal p normal t left-parenthesis upper G right-parenthesis less-than-or-equal-to upper O l