Improved upper bounds on longest-path and maximal-subdivision transversals

Abstract: Let

G

be a connected graph on

n

vertices. The Gallai number

G a l (G)

of

G

is the size of the smallest set of vertices that meets every maximum path in

G

. Gr"unbaum constructed a graph

G

with

G a l (G) = 3

. Very recently, Long, Milans, and Munaro, proved that

G a l (G) l e q 8 n^{3 / 4}

. This was the first sublinear upper bound on

G a l (G)

in terms of

n

. We improve their bound to

G a l (G) l e q 5 n^{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 g e q m^{6}

, then

G

has a set of vertices with size at most

5 n^{2 / 3}

that meets every

Q i n m a t h c a l L (M, G)

Recommendations

Cites Work

Cited In (1)

This page was built for publication: Improved upper bounds on longest-path and maximal-subdivision transversals