Vis enkel innførsel

dc.contributor.authorCerioli, Marcia R.
dc.contributor.authorFernandes, Cristina G.
dc.contributor.authorGómez, Renzo
dc.contributor.authorGutiérrez, Juan
dc.contributor.authorLima, Paloma T.
dc.date.accessioned2021-06-14T12:01:27Z
dc.date.available2021-06-14T12:01:27Z
dc.date.created2020-02-19T10:42:03Z
dc.date.issued2020-03
dc.identifier.issn0012-365X
dc.identifier.urihttps://hdl.handle.net/11250/2759300
dc.description.abstractLet 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.isoengen_US
dc.publisherElsevieren_US
dc.titleTransversals of longest pathsen_US
dc.typeJournal articleen_US
dc.typePeer revieweden_US
dc.description.versionacceptedVersionen_US
dc.rights.holderCopyright 2019 Elsevieren_US
dc.source.articlenumber111717en_US
cristin.ispublishedtrue
cristin.fulltextpostprint
cristin.qualitycode1
dc.identifier.doi10.1016/j.disc.2019.111717
dc.identifier.cristin1795711
dc.source.journalDiscrete Mathematicsen_US
dc.identifier.citationDiscrete Mathematics. 2020, 343 (3), 111717en_US
dc.source.volume343en_US
dc.source.issue3en_US


Tilhørende fil(er)

Thumbnail

Denne innførselen finnes i følgende samling(er)

Vis enkel innførsel