Transversals of longest paths
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.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 |
Tilhørende fil(er)
Denne innførselen finnes i følgende samling(er)
-
Department of Informatics [899]
-
Registrations from Cristin [9371]