Sublinear Longest Path Transversals

Jr James A. Long, Kevin G. Milans, Andrea Munaro

Research output: Contribution to journalArticlepeer-review

2 Citations (Scopus)
134 Downloads (Pure)

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 languageEnglish
Pages (from-to)1673–1677
JournalSIAM Journal on Discrete Mathematics
Volume35
Issue number3
DOIs
Publication statusPublished - 27 Jul 2021

Fingerprint

Dive into the research topics of 'Sublinear Longest Path Transversals'. Together they form a unique fingerprint.

Cite this