Sublinear Longest Path Transversals

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

Research output: Contribution to journalArticlepeer-review

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