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. - In: SIAM JOURNAL ON DISCRETE MATHEMATICS. - ISSN 0895-4801. - 35:3(2021), pp. 1673-1677. [10.1137/20M1362577]
Sublinear longest path transversals
Andrea Munaro
2021-01-01
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.File in questo prodotto:
| File | Dimensione | Formato | |
|---|---|---|---|
|
Sublinear Longest Path Transversals.pdf
accesso aperto
Tipologia:
Documento in Post-print
Licenza:
Creative commons
Dimensione
200.49 kB
Formato
Adobe PDF
|
200.49 kB | Adobe PDF | Visualizza/Apri |
|
159-Munaro-20m1362577.pdf
solo utenti autorizzati
Tipologia:
Versione (PDF) editoriale
Licenza:
NON PUBBLICO - Accesso privato/ristretto
Dimensione
264.39 kB
Formato
Adobe PDF
|
264.39 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
