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

H. A. Kierstead; E. R. Ren

doi:10.1016/j.disc.2023.113514

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

H. A. Kierstead
, E. R. Ren

Mathematical and Statistical Sciences, School of (SoMSS)

Research output: Contribution to journal › Article › peer-review

1 Scopus citations

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)≤8n^3/4. This was the first sub-linear upper bound on Gal(G) in terms of n. We improve their bound to Gal(G)≤5n^2/3. We also tighten a more general result of Long et al.

Original language	English (US)
Article number	113514
Journal	Discrete Mathematics
Volume	346
Issue number	9
DOIs	https://doi.org/10.1016/j.disc.2023.113514
State	Published - Sep 2023

Keywords

Gallai number
Gallai's problem
Longest path
Path transversals

ASJC Scopus subject areas

Theoretical Computer Science
Discrete Mathematics and Combinatorics

Access to Document

10.1016/j.disc.2023.113514

Cite this

@article{e81f6b39718f4a2795540de356a965d5,

title = "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{\"u}nbaum constructed a graph G with Gal(G)=3. Very recently, Long, Milans, and Munaro, proved that Gal(G)≤8n3/4. This was the first sub-linear upper bound on Gal(G) in terms of n. We improve their bound to Gal(G)≤5n2/3. We also tighten a more general result of Long et al.",

keywords = "Gallai number, Gallai's problem, Longest path, Path transversals",

author = "Kierstead, \{H. A.\} and Ren, \{E. R.\}",

note = "Funding Information: We thank a referee for suggesting that we extend our original argument for longest-path transversals to maximum-subdivision transversals. Publisher Copyright: {\textcopyright} 2023 Elsevier B.V.",

year = "2023",

month = sep,

doi = "10.1016/j.disc.2023.113514",

language = "English (US)",

volume = "346",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier",

number = "9",

}

TY - JOUR

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

AU - Kierstead, H. A.

AU - Ren, E. R.

N1 - Funding Information: We thank a referee for suggesting that we extend our original argument for longest-path transversals to maximum-subdivision transversals. Publisher Copyright: © 2023 Elsevier B.V.

PY - 2023/9

Y1 - 2023/9

N2 - 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)≤8n3/4. This was the first sub-linear upper bound on Gal(G) in terms of n. We improve their bound to Gal(G)≤5n2/3. We also tighten a more general result of Long et al.

AB - 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)≤8n3/4. This was the first sub-linear upper bound on Gal(G) in terms of n. We improve their bound to Gal(G)≤5n2/3. We also tighten a more general result of Long et al.

KW - Gallai number

KW - Gallai's problem

KW - Longest path

KW - Path transversals

UR - https://www.scopus.com/pages/publications/85159847911

UR - https://www.scopus.com/pages/publications/85159847911#tab=citedBy

U2 - 10.1016/j.disc.2023.113514

DO - 10.1016/j.disc.2023.113514

M3 - Article

SN - 0012-365X

VL - 346

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 9

M1 - 113514

ER -

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

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this