Improved upper bounds on longest-path and maximal subdivision transversals

Abstract

Let $G$ be a connected graph on $n$ vertices. The Gallai number $Gal(G)$ of $G$ is the size of the smallest set of vertices that meets every maximum path in $G$. Grünbaum constructed a graph $G$ with $Gal(G)=3$. Very recently, Long, Milans, and Munaro, proved that $Gal(G)\le 8n^{3/4}$. This was the first sublinear upper bound on $Gal(G)$ in terms of $n$. We improve their bound to $Gal(G)\le 5n^{2/3}$. We also tighten a more general result of Long et al. For a multigraph $M$ on m edges, we prove that if the set $L(M,G)$ of maximum $M$-subdivisions in $G$ is pairwise intersecting and $n\ge m^6$, then $G$ has a set of vertices with size at most $5n^{2/3}$ that meets every $Q\in \mathcal{L}(M,G)$

To be published in Discrete Mathematics

Cited by in corpus (1)

• Longest cycles in vertex-transitive and highly connected graphs