Abstract
We show that connected graphs admit sublinear longest path transversals. This improves an earlier result of Rautenbach and Sereni and is related to the fifty-year-old question of whether connected graphs admit longest path transversals of constant size. The same technique allows us to show that 2-connected graphs admit sublinear longest cycle transversals.
Original language | English |
---|---|
Pages (from-to) | 1673–1677 |
Journal | SIAM Journal on Discrete Mathematics |
Volume | 35 |
Issue number | 3 |
DOIs | |
Publication status | Published - 27 Jul 2021 |