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.

Sublinear longest path transversals / A. Long Jr., James; Milans, Kevin G.; Munaro, Andrea. - 35:3(2021), pp. 1673-1677. [10.1137/20M1362577]

Sublinear longest path transversals

Andrea Munaro
2021

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.
Sublinear longest path transversals / A. Long Jr., James; Milans, Kevin G.; Munaro, Andrea. - 35:3(2021), pp. 1673-1677. [10.1137/20M1362577]
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11381/2930773
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? 0
social impact