Small hitting sets for longest paths and cycles

Sergey Norin, Raphael Steiner, Stéphan Thomassé, Paul Wollan · 2025

Read Small hitting sets for longest paths and cycles by Sergey Norin, Raphael Steiner, Stéphan Thomassé, Paul Wollan (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-08634.txt.

Introduction

Sergey Norin, Raphael Steiner, Stéphan Thomassé, and Paul Wollan ask how few vertices can touch every longest path in a graph. An old question of Gallai asked whether all longest paths share one common vertex. They rarely do, so the next best thing is a small hitting set.

The team proves that in any connected graph on n vertices, a hitting set of size at most the square root of 8n always exists for longest paths. For cycles in twice-connected graphs, the same bound holds. A second bound ties the hitting set to the longest path's own length. These sharpen a chain of older results. The work also bears on conjectures about paths in highly symmetric graphs. Small sets tame global structure here.

Catalog record

CREATORSergey Norin, Raphael Steiner, Stéphan Thomassé, Paul Wollan
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE47 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2505-08634

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Small hitting sets for longest paths and cycles Sergey Norin, Raphael Steiner, Stéphan Thomassé, Paul Wollan Abstract Motivated by an old question of Gallai (1966) on the intersection of longest paths in a graph and the well-known 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 lpt ⁡ ( G ) \mathrm{lpt}(G) and lct ⁡ ( 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 lpt ⁡ ( G ) ≤ 8 ​ n \mathrm{lpt}(G)\leq\sqrt{8n} , and lct ⁡ ( G ) ≤ 8 ​ n \mathrm{lct}(G)\leq\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 lpt ⁡ ( G ) ≤ O ⁡ ( ℓ 5 / 9 ) \mathrm{lpt}(G)\leq O(\ell^{5/9}) , where ℓ \ell denotes the maximum length of a path in G G . As an immediate application of this latter bound, we present further progress towards Lovász conjecture: We show that every connected vertex-transitive graph of order n n contains a path of length Ω ⁡ ( n 9 / 14 ) \Omega(n^{9/14}) . This improves the previous best bound of the form Ω ⁡ ( n 13 / 21 ) \Omega(n^{13/21}) . Interestingly, our proofs make use of several concepts and results from structural graph theory, such as a result of Robertson and Seymour (1990) on transactions in societies and Tutte’s 2 2 -separator theorem. 1 Introduction A well-known folklore fact states that in a connected graph G , any two longest paths 1 1 1 Throughout this paper, when speaking of a longest path (cycle) , we mean a path (or cycle) that attains the maximum possible length among all paths (or cycles) in the graph. must share a common vertex. This motivated Gallai [ 12 ] in 1966 to ask if an even stronger statement could be true, namely whether in every connected graph there is a vertex that belongs to all longest paths. To discuss this question in a more general context, it will be convenient to denote by \mathrm{lpt}(G) and \mathrm{lct}(G) respectively, the minimum size of a longest path transversal and the minimum size of a longest cycle transversal of G , respectively, that is, a subset of vertices S\subseteq V(G) such that every longest path (cycle) in G contains at least one vertex from S . Gallai’s question then can be restated as asking whether \mathrm{lpt}(G)=1 for every connected graph G . While the answer has been shown to be positive for many special classes of graphs, see [ 3 , 6 , 7 , 8 , 10 , 13 , 16 , 17 , 19 , 21 , 25 , 33 ] , it is known to be negative in general, as was first shown by Walther [ 31 ] in 1969, who constructed a connected graph G on 25 vertices with \mathrm{lpt}(G)=2 . The currently smallest example of a graph G with the same property has 12 vertices, as found by Walther [ 32 ] and Zamfirescu [ 35 ] . A graph with no longest path transversal of size 2 was found in 1974 by Grünbaum [ 15 ] . The smallest known construction of a graph with \mathrm{lpt}(G)=3 is due to Zamfirescu [ 35 ] . Quite amazingly, no connected graph G satisfying \mathrm{lpt}(G)>3 has been found in the last half century since Grünbaum’s example. In particular, the tantalizing question, raised independently by Walther and Zamfirescu [ 34 ] , whether there exists an absolute constant c>0 such that every connected graph G satisfies \mathrm{lpt}(G)\leq c , remains widely open. The situation and state of the art for longest cycle transversals is analogous to that of longest path transversals, except that here the natural setting to study the question is given by 2 -connected graphs: In 2 -connected graphs any two longest cycles are guaranteed to intersect, while this is not in general the case in connected graphs. Further, it is easy to construct examples of connected n -vertex graphs where every longest cycle transversal must have size \Theta(n) . We refer to the survey articles [ 29 , 36 ] for more details on the known lower bound examples for longest cycle transversals. Let P,C:\mathbb{N}\rightarrow\mathbb{N} denote the smallest functions such that every n -vertex ( 2 -)connected graph has a longest path (cycle) transversal of size at most P(n) (at most C(n) ), respectively. As mentioned above, the best known lower bounds on P(n) and C(n) are constant, which raises the question whether one can conversely prove good upper bounds on P(n) and C(n) . Another motivation for upper-bounding P(n) and C(n) was recently noted by Groenland et al. [ 14 ] (see also [ 2 , 11 ] ). Two famous conjectures due to Lovász [ 26 ] from 1969 and Thomassen (cf. [ 4 ] ) from 1978 postulate that all (sufficiently large) connected vertex-transitive graphs admit a Hamiltonian path (cycle). These tantalizing conjectures have received a lot of attention by many researchers in the last 50 years, but yet remain widely open today. In particular, it is not known whether every connected vertex-transitive graph of order n contains a path of length \Omega(n) . We refer to [ 1 , 22 ] for surveys on the partial results towards Lovász’ and Thomassen’s conjectures. One can observe (cf. [ 14 , Proposition 5.1] ) that every connected vertex-transitive graph of order n contains a path of length at least \frac{n}{P(n)}-1 and a cycle of length at least \frac{n}{C(n)} . Thus, any progress on the asymptotic upper bounds on P(n) and C(n) can be converted into progress on finding long paths and cycles in vertex-transitive graphs. The first non-trivial upper bounds on P(n) and C(n) were obtained by Rautenbach and Sereni [ 27 ] , who showed that P(n)\leq\left\lceil\frac{n}{4}-\frac{n^{2/3}}{90}\right\rceil and C(n)\leq\left\lceil\frac{n}{3}-\frac{n^{2/3}}{36}\right\rceil . Recently, both of these bounds were asymptotically improved, first to the sublinear bounds P(n)=O(n^{3/4}) and C(n)=O(n^{3/4}) by Long, Milans and Munaro [ 24 ] , and then further to P(n)=O(n^{2/3}) and C(n)=O(n^{2/3}) by Kierstead and Ren [ 20 ] . In this paper, we further reduce both upper bounds to O(\sqrt{n}) . Additionally, we provide a new upper bound for longest path transversals in terms of the length \ell of a longest path instead of the number of vertices. Theorem 1 . (i) Let G be a connected graph on n\geq 2 vertices and let \ell denote the maximum length of a path in G . Then \mathrm{lpt}(G)\leq\min\{\sqrt{8n},33\cdot\ell^{5/9}\}. (ii) For every 2 -connected graph G on n vertices, we have \mathrm{lct}(G)\leq\sqrt{8n} . As a direct Corollary of Theorem 1 (i) we deduce a new lower bound for the length of longest paths in connected vertex-transitive graphs with n vertices, thus making further progress on Lovász conjecture [ 26 ]

Read the complete text