dc.contributor.author Cerioli, Marcia R. dc.contributor.author Fernandes, Cristina G. dc.contributor.author Gómez, Renzo dc.contributor.author Gutiérrez, Juan dc.contributor.author Lima, Paloma T. dc.date.accessioned 2021-06-14T12:01:27Z dc.date.available 2021-06-14T12:01:27Z dc.date.created 2020-02-19T10:42:03Z dc.date.issued 2020-03 dc.identifier.issn 0012-365X dc.identifier.uri https://hdl.handle.net/11250/2759300 dc.description Postponed access: the file will be accessible after 2021-11-20 en_US dc.description.abstract Let lpt(G) be the minimum cardinality of a transversal of longest paths in G, that is, a set of vertices that intersects all longest paths in a graph G. There are several results in the literature bounding the value of lpt(G) in general or in specific classes of graphs. For instance, lpt(G) = 1 if G is a connected partial 2-tree, and a connected partial 3-tree G is known with lpt(G) = 2. We prove that lpt(G) ≤ 2 for every planar 3-tree G; that lpt(G) ≤ 3 for every connected partial 3-tree G; and that lpt(G) = 1 if G is a connected bipartite permutation graph or a connected full substar graph. Our first two results can be adapted for broader classes, improving slightly some known general results: we prove that lpt(G) ≤ k for every connected partial k-tree G and that lpt(G) ≤ max{1, ω(G) − 2} for every connected chordal graph G, where ω(G) is the cardinality of a maximum clique in G. en_US dc.language.iso eng en_US dc.publisher Elsevier en_US dc.title Transversals of longest paths en_US dc.type Journal article en_US dc.type Peer reviewed en_US dc.description.version acceptedVersion en_US dc.rights.holder Copyright 2019 Elsevier en_US dc.source.articlenumber 111717 en_US cristin.ispublished true cristin.fulltext postprint cristin.qualitycode 1 dc.identifier.doi 10.1016/j.disc.2019.111717 dc.identifier.cristin 1795711 dc.source.journal Discrete Mathematics en_US dc.identifier.citation Discrete Mathematics. 2020, 343 (3), 111717 en_US dc.source.volume 343 en_US dc.source.issue 3 en_US
﻿