2023/05/08 by Henry A. Kiersteád, Kierstead, Henry, Eric Ren +1 · 3 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Coding theory and cryptography #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2305.05045
openalex publication_date 2023/05/08 · openalex created_date 2023/05/12 · openalex updated_date 2026/07/28
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)≤ 8n^3/4. This was the first sublinear upper bound on Gal(G) in terms of n. We improve their bound to Gal(G)≤ 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≥ m6, then G has a set of vertices with size at most 5 n^2/3 that meets every Q∈ L(M,G)